[C++로 풀이] 야근 지수 ⭐⭐⭐

📌 야근 지수

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;

    sort(works.begin(), works.end()); // 오름 차순 정렬

    while (n > 0 && works[0] != 0) {
        // 최대값 범위 찾기
        int count = 1;
        int delta = 0;
        int index = 0;
        for (int i = works.size() - 1; ; i--) {  // 반복 조건 안씀 주의 (else 에 해당할때만 break)
            if (i > 0 && works[i - 1] == works[i])
                count++;
            else { 
                delta = works[i] - works[i - 1];
                index = i;
                break;
            }
        }

        // 최대값들에서 균등하게 빼주기
        if (n / count >= delta) {
            for (int i = 0; i < count; i++)
                works[index + i] -= delta;
            n -= count * delta;
        }
        else {
            for (int i = 0; i < count; i++)
                works[index + i] -= n / count;
            for (int i = 0; i < n % count; i++)
                --works[index + i];
            n = 0;
        }
    }

    for (int i = 0; i < works.size(); ++i)
        answer += (long long)works[i] * works[i];
    return answer;
}

야근 지수를 최소화하려면 works의 모든 원소들끼리 균등해지는 방향으로 n만큼 빼야한다. [1,2,3] 보단 [2,2,2] 의 야근 지수가 더 작다. 균등하게 만드는 것이 중요.

• ✨ 균등하게 만드려면?
  • 먼저 오름차순 정렬한다.

    sort(works.begin(), works.end());
    

  • 아래 과정을 반복한다 .(최대값들이 두 번째로 큰 것과 같아지게끔!)
    • 반복 조건
      • 다 빼서 n이 0 이 되거나 OR
      • n을 다 못쓰더라도 작업이 다 끝났다면, 즉 works[0]이 0이 되었거나 하면 반복을 종료한다.
    • 1️⃣ 최대값 범위 찾기 (최대값은 중복된 여러개가 있을 수 있음)
      • [1,2,7,9,9,9,9] 라면 첫번째 for문을 다 돌고나면 index는 최대값 9가 시작되는 4 가 되며 (4부터 끝까지가 최대값 범위) 두번째로 큰것과의 차이를 뜻하는 delta는 9 - 7 = 2가 된다. count는 최대값이 4개이므로 4 가 된다.
    • 2️⃣ 균등해지게끔 최대값들에게 빼주기.
      • n이 허락하는 선에서 [1,2,7,9,9,9,9] 에서 [1,2,7,7,7,7,7] 가 되는 것이 목표. 최대값인 4개의 9들에서 2씩을 빼서 7로 다 균등하게 만들어야 한다. 즉 현재의 works 범위에서 두 번째로 큰 것과 같아지게끔 최대값들에서 뺀다.
        • 1️⃣ n / count >= delta 인 경우
          • n이 현재 10 이라면(즉 현재 10시간 작업 가능) 10 / 4 >= 2 이므로 4개의 최대값들에서 2씩 빼서 7로 만들 수 있다!
            • [1,2,7,9,9,9,9] 에서 4 * 2 = 8 (count * delta) 시간만큼을 소모하여 4개의 9마다 각각 2씩 빼주어 [1,2,7,7,7,7,7] 로 만들 수 있다. n은 10 시간에서 8시간 소모했으니 n = 2가 된다. (다음 while문에서 이제 2가 된 n으로 처리)

              if (n / count >= delta) {
                for (int i = 0; i < count; i++)
                    works[index + i] -= delta;
                n -= count * delta;
              }
              

        • 2️⃣ n / count < delta 인 경우
          • n이 현재 7이라면(즉 현재 7시간 작업 가능) 7 / 4 < 2 이므로 n을 균등하게 만드는데 전부 다 써야 한다. (즉 7 다써서 n은 0이 되야함) 또한 최대값 4개가 전부 균등해지진 못할 수도 있다.
            • [1,2,7,9,9,9,9] 에서 7 값인 n을 전부 소모하여 7 을 4 로 나눈 몫은 1 이므로 4개의 9에서 몫인 1씩 빼줄 수 있다. 그리고 나머지 7 % 4 는 3이므로 4개의 9중에서 3개는 1씩 더 빼줄 수 있다.

              else {
                for (int i = 0; i < count; i++)
                    works[index + i] -= n / count;
                for (int i = 0; i < n % count; i++)
                    --works[index + i];
                n = 0;
              }
              

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기