6719. 성수의 프로그래밍 강좌 시청(D4)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWd7sgDatsMDFAUh&categoryId=AWd7sgDatsMDFAUh&categoryType=CODE

강의의 수 n과 들을 수 있는 강의의 수 k가 주어진다. ( k<=n )

우선, 강의의 효율을 최대로 하는 것이기 때문에 가장 효율이 큰 k개의 강의를 들어야 한다는 것을 알 수 있다.

다음으로 강의를 들을 때마다 (기존의 학습량 + 새로운 강의의 학습량 / 2)가 된다.

즉, 처음 강의는 2^k만큼 나누어지고 다음 강의는 2^(k-1)으로 나누어지는 방식으로 진행된다.

그렇기 때문에 듣기로 정한 k개의 강의 중 가장 효율이 낮은 강의부터 순서대로 듣는 것이 최대의 결과를 낸다는 것을 알 수 있다.

이렇게 구상한 방법을 실제로 구현해보자.

1. 가장 효율이 큰 k개의 강의 구하기.

-> 사용한 방법은 강의의 최대 효율이 10000이므로 효율에 따라 배열을 만들어서 n개의 강의를 입력받을 때마다 해당 효율의 count를 늘려준다.

-> 앞에서부터 탐색하며 전부 스택에 넣는다.

-> 새로운 스택에 k개만큼 pop하여 push한다.

2. 만들어진 stack을 pop하며 result에 더하고 2로 나눈다.

* 강의의 개수가 적기 때문에 편의를 위해 새로운 stack에 넣는 방법을 사용했지만 이 방법은 효율적이지 않다.

* 강의의 개수가 많을 경우에는 스택을 1개만 두고 배열을 뒤에서부터 탐색하며 k개만큼 push하는 방법을 사용하는 것이 더 좋다.

+ 값이 들어있는 index 번호를 저장해둔다면 저장된만큼 메모리는 증가하지만 시간복잡도는 줄일 수 있다.

---

- 소스 코드 -

#include <iostream>
 
class myStack{
    public:
    int stack[201]={0};
    int top=0;
    
    void push(int k){
        stack[top]=k;
        top++;
    }
    
    int pop(){
        top--;
        return stack[top];
    }
    
    int check_top(){
        return top;
    }
};
 
int main()
{
  int T;
  scanf("%d",&T);
  for(int test_case=1;test_case<=T;test_case++){
    int arr[10002]={0};
    
    int n,k;
    scanf("%d %d",&n,&k);
    
    myStack m_stack1;
    myStack m_stack2;
    
    for(int i=0;i<n;i++){
        int temp;
        scanf("%d",&temp);\
        arr[temp]++;
    }
    
    for(int i=0;i<=10001;i++){
        if(arr[i]==0)continue;
        else{
            while(arr[i]!=0){
                m_stack1.push(i);
                arr[i]--;
            }
        }
    }
 
    int count=0;
    while(count<k){
        m_stack2.push(m_stack1.pop());
        count++;
    }
    
    float result=0;
    
    while(m_stack2.check_top()!=0){
        result+=(float)m_stack2.pop();
        result/=(float)2;
    }
    printf("#%d %.6f\n",test_case,result);
  }
}
 

---