[프로그래머스 3단계] 알고리즘 31. 야근지수

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 31. 야근 지수

회사원인 수민이는 많은 일이 쌓여 있습니다. 수민이는 야근을 최소화하기 위해 남은 일의 작업량을 숫자로 메기고, 일에 대한 야근 지수를 줄이기로 결정했습니다. 야근 지수는 남은 일의 작업량을 제곱하여 더한 값을 의미합니다. 수민이는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 수민이의 퇴근까지 남은 N 시간과 각 일에 대한 작업량이 있을 때, noOvertime 함수를 제작하여 수민이의 야근 지수를 최소화 한 결과를 출력해 주세요. 예를 들어, N=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 일을 한 결과는 [2, 2, 2]가 되고 야근 지수는 22+ 22 + 22 = 12가 되어 12를 반환해 줍니다.

#include<iostream>

#include<vector>

using namespace std;

int noOvertime(int no,vector<int> works)

{

    int answer = 0;

    return 0;

}

int main()

{

    vector<int> works{4,3,3};

    int testNo = 4;

    int testAnswer = noOvertime(testNo,works);

    cout<<testAnswer;

}

풀이:

이 문제의 핵심은 남은 시간 동안 현재 남은 작업량 중에서 제일 많이 남은 작업을 처리하는 것이다. 여기서 포인트는 작업을 처리 할 때마다 남은 작업량을 내림차순으로 계속 정렬해주어야 한다. 예제를 보면서 이해해보자,

남은 시간 : 4

작업 : [4, 3, 3]

최대 남은 작업량 : 4

-> [3, ,3, 3] 1시간 사용 

남은 시간 : 3

작업 : [3, 3, 3]

최대 남은 작업량 : 3

-> [2, 3, 3] 1시간 사용 -> 내림차순 정렬

남은 시간 : 2

작업 [3, 3, 2] 

최대 남은 작업량 : 3

-> [2, 3, 2] 1시간 사용 -> 내림차순 정렬

남은 시간 : 1

작업 : [3, 2, 2]

최대 남은 작업량 : 3

-> [2, 2, 2] 1시간 사용

남은 시간 : 0

작업 : [2, 2, 2]

야근 지수 : 4 + 4 + 4 = 12

코드는 다음과 같다.

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

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

int noOvertime(int no,vector<int> works)

{

int answer = 0;

for (int i=0; i<no; i++)

{

sort(works.begin(), works.end(), is_descending);    //역순 정렬     

works[0] -= 1;

}

answer = accumulate(works.begin(), works.end(), 0, [](int a, int b){ return a + (b * b);} );     //제곱 합 계산

   return answer;

}

int main()

{

    vector<int> works{4,3,3};

    int testNo = 4;

    int testAnswer = noOvertime(testNo,works);

    cout<<testAnswer;

}

이 문제에서 STL 중 하나인 알고리즘 라이브러리를 썼다. sort 함수는 이전에 설명한 적이 있을 것이다. 이번엔 accumulate 함수를 써서 결과를 누적 시켰는데 accumulate는 인자로 컨테이너 시작점, 컨테이너 종료점, 초기값, 누적시킬 방법을 받는다. 따라서 works 처음부터 끝까지 0부터 시작해서 벡터 요소의 제곱의 합(C++ 람다로 처리)을 누적시켜준다. 따라서 답을 구할 수 있다. 나는 이번 문제를 2시간 정도 풀다가 도저히 안돼서 인터넷을 찾아보았는데... 이렇게 쉬운 문제였을 줄이야 OTL 더 공부를 열심히 하자.