[알고리즘문제] 프로그래머스 -멀리 뛰기

문제는 한번 읽어서 바로 이해가 안되서 두 세번정도 읽었습니다.

 

문제에서 남은 작업량, 남은 N시간이 주어지고 야근피로도 구하는 공식(남은 작업량들의 각각 제곱근의 합)이 주어질 때 최소한의 야근 피로도를 구하는 문제 입니다. 단 1시간에 1의 일을 할 수 있습니다.

 

예를 들어 남은 작업량이 [4,3,3]이고 N시간이 주어졌을 때 4시간 동안일을 했을 때 남은 작업량의 경우의 수는 다음과 같습니다.

 

[4,2,2]

[3,0,3]

[2,2,2]

....

 

이 경우에서 야근 피로도를 구해보면

 

[4,2,2] = 4^2 + 2^2 + 2^2 = 24

[3,0,3] = 3^2 + 0^2 + 3^2 = 18

[2,2,2] = 2^2 + 2^2 + 2^2=12

 

더 많은 경우가 있겠지만 위의 경우에서 야근 피로도가 최소값이 되는 경우는 [2,2,2]입니다. 이때의 야근피로도 12를 return 하면 됩니다.

 

저는 두가지의 방법을 생각해 보았는데, 아마 비슷한 이유때문에 둘다 통과하지 못했던 것 같습니다. 결국에는 다른 사람의 코드를 참고하였습니다. 아이디어는 비슷했는데 세세한 부분에서 차이가 있었습니다.

 

1. 시간이 남아 있는 동안 남아있는 작업량들을 하나씩 -1해주는 방법

-> 작업량이 아주 낮은 값보다는 큰 값을 빼주는게 더 효율적임.

 

2. 작업량을 내림차순으로 정렬하고, 작업량 중 최소작업량을 구하고 시간이 남아있는 동안 각 작업량을 최소작업량에 가깝에 빼주는 방법입니다.

-> 작업량이 큰 값을 한번에 빼주는 것 보단 여러 큰 값들을 똑같이 빼주는 것이 효율적임

 

 

정답은 1의 방법에서 좀 진화한 방법인데 모든 작업량을 -1해주는 것보다는 max heap을 사용하여 최대값을 -1해주는 방법을 사용합니다.

작업량이 큰 값을 한번에 뺴주는 것보다는 "여러 큰 값들을 -1"해주는 방법이 전체 피로도를 줄이는데 더 효율적입니다. 어쨋든 다른 작업량 값이 낮아도 하나의 큰 값이 엄청 커버리면 피로도가 증가하니깐요.

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

long long solution(int n, vector<int> works) {
    
    priority_queue<int, vector<int>, less<int>> maxHeap(works.begin(),works.end());
    
    while(n--){
        if(maxHeap.top() > 0){
            int max = maxHeap.top();
            maxHeap.pop();
            maxHeap.push(max-1);
        }
    }
    
    long long answer = 0;
    
    while(!maxHeap.empty()){
        int top = maxHeap.top();
        maxHeap.pop();
        answer +=(long long)top * (long long)top;
    }
    return answer;
}