[프로그래머스 야근지수] c++ (풀이,코드)

문제 링크

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

프로그래머스

 

문제

 

코드, 풀이

우리는 x가지의 숫자가 가장 같게 하여야 제곱의 합에서 가장 낫다는 것을 알 수 있습니다.

 

문제가 주어진 예시를 보시게 되면

works	n	result
[4,3,3]	4	12
[2,1,2]	1	6
[1,1]	3	0

결국 x가지의 숫자를 가장 같게 만들어야 합니다

[4,3,3] , 4 -> [2,2,2]

[2,1,2] 1 -> [2,1,1] 이런식으로 만들어야 한다고 생각합니다.

 

해결 순서

1. 먼저 works를 역순으로 sort를 해줍니다.

2. 반복문에 n >0일때까지 반복문을 돌려줍니다

   1) 만약 works[idx] <= works[idx + 1]이라면 idx++을 해줍니다.

   2) else -> 0부터 같은 숫자에서 1씩 차감을 해줍니다  0~idx까지 하나씩 -- (단, n>0일때까지)

 

 

/*

남은 일의 작업량을 제곱하여 더함 -> 피로도

제곱의 합을 더하는 건데 결국 가장 평균에 가깝게 숫자들을 빼면 되는것.

*/

#include <string>

#include <vector>

#include <cmath>

#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;

    int workSum = 0;

   

   

    for(int i = 0; i < works.size();i++)

        workSum += works[i];

    if(workSum <= n)

        return 0;

   

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

    // 9 9 9 8 8 7 6 2 2 1

    int idx = 0;

    while(n > 0){

        if(works[idx] <= works[idx + 1]){

            idx++;

        }else{

            for(int i = 0; i <= idx; i ++){

                if(n >0){

                    works[i]--;

                    n--;

                }

            }

        }

    }

   

    for(int i = 0; i < works.size();i++)

        answer += pow(works[i], 2);

    return answer;

}