문제

• 마력이 담긴 아이템이 n개 주어집니다.
• 아이템을 사용하면 마력이 1씩 줄어들면서 0이 되면 아이템이 사라집니다.
• 아이템을 m번 사용해서 얻을 수 있는 최대 마력의 양을 구하시오.
• n(1 <= n <= 100) 아이템의 개수 , m(1 <= n <= 1만) 아이템 사용 횟수
• 시간 제한 10초
• 문제 링크

접근 과정

1. 그리디

• 문제를 보고 가장 먼저 느껴지는 것은 굉장히 그리디스럽다. 왠지 제일 마력이 높은 것만 계속 먹으면 될 것 같습니다. 근데, 뭔가 문제가 잘 이해되지 않았습니다. 댓글을 보니 저만 그런게 아니었던것 같습니다.
• 과정을 정리해보면
  1) 배열의 아이템을 내림차순으로 정렬합니다.
  2) 제일 마력이 많이 들어 있는 아이템을 마십니다. 그리고 그 아이템은 사용했기 때문에 마력을 1감소 시킵니다.
  3) 1), 2) 과정을 m번 수행합니다.
• 왜 이해가 안됐냐면, 마력을 마시는데 필요한 시간 == 감소에 필요한 시간...
  만약,
  1) m 사용할 수 있는 시간(단위 초),
  2) 마력을 마시는데 필요한 시간 1초,
  3) 아이템은 사용하면 1초에 1씩 감소하다가 마력이 0이 되면 사라집니다.
  이라고 했으면 이해가 쉬웠을것 같다.

2. 시간 복잡도 계산

• 1) n개의 아이템을 정렬하는 시간 O(nlogn) * m번 수행 = O(mnlogn)

• n(1 <= n <= 100) 아이템의 개수 , m(1 <= n <= 1만) 아이템 사용 횟수 이기 때문에 O(mnlogn)은 O(100 * 100 * 10) = O(10만) 문제의 시간 제한이 10초 이기 때문에 시간이 남아돕니다.

코드

1. C++

#include <iostream>
#include <algorithm>

#define max_int 101
using namespace std;

//시간 복잡도: O(mnlogn)
//공간 복잡도: O(n)
//사용한 알고리즘: 그리디, STL sort
//사용한 자료구조: 배열


int t, n, m, result;
// 아이템 정보를 담는 배열
int a[max_int];

int main(){
    scanf("%d", &t);

    for(int test_case = 1; test_case <=t; test_case++){

        // 1. 변수 초기화
        result = 0;

        // 2. 정보를 입력받는다.
        scanf("%d %d", &n, &m);
        for(int i=0; i<n; i++){
            scanf("%d", &a[i]);
        }

        // 3. m번 만큼 아이템을 사용합니다.
        while(m--){
            // 마력 내림차순으로 정렬
            sort(a, a+n, greater<int>());

            // 제일 마력이 많이 들어있는 아이템을 사용합니다.
            result += a[0];

            // 마력은 0이 되면 없어집니다.
            if(a[0] > 0) a[0]--;
        }

        // 4. 결과 출력
        printf("%d\n", result);
    }
}