프로그래머스 - 12927 야근 지수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12927#

프로그래머스

야근을 하고 남은 일의 제곱의 합의 최솟값을 구하는 문제였다.

문제 풀이

남은 일의 제곱의 합을 구해야 하기 때문에 큰 수를 최대한 줄여야 했다. 

만약 works가 [10, 10, 8, 6, 4]가 있고 N이 5라면 합이 최소가 되기 위해서는 일을 한 결과가 [8,8,7,6,4]가 되어야 한다.

 

이렇게 하기 위해서 먼저 works를 내림차순으로 정렬했고, N만큼 반복하면서 현재 work에서 1을 빼주고 다음 수로 넘어갔다. 항상 가장 큰 값에서 1을 빼기 위해 만약 다음 수가 현재 작업을 완료한 수보다 작을 경우에 다시 index를 맨 앞으로 옮겨줬다. 이를 N만큼 반복하고 나온 works 결과물이 최종 남은 일의 작업량이고, 이 값들의 제곱의 합이 답이 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b){
    return a>b;
}

//야근 피로도 : 남은일 제곱의 합
long long solution(int n, vector<int> works) {
    long long answer = 0;
    
    sort(works.begin(), works.end(), compare);
    
    int nowIndex = 0;
    for(int i=0;i<n;i++){
        int nextIndex = nowIndex+1;
        
        if(works[nowIndex] == 0){ //모든 작업 완료!
            break;
        }
        works[nowIndex]--;
        if(nextIndex >= works.size()){ //다음 수가 없음 -> 0으로 돌아가기
            nextIndex = 0;
        }
        if(works[nowIndex] >= works[nextIndex]){ //큰 수 -1 완료함 -> 0으로 가기
            nextIndex = 0;
        }
        
        nowIndex = nextIndex;        
    }
    
    for(int i=0;i<works.size();i++){
        answer += (works[i] * works[i]);
    }
    
    return answer;
}