[DAY79] Algorithm : Overtime index

이번 포스트에서는 야근 피로도를 최소화하는 문제를 그리디(Greedy) 알고리즘으로 해결한 과정을 정리했다. 피로도를 최소화하려면 가장 큰 작업량을 우선적으로 처리해야 한다는 직관을 바탕으로 풀이를 시작했다. 최댓값 추출에는 일반적으로 std::priority_queue가 쓰이지만, 이번에는 직전 포스트에서 학습한 std::multiset과 prev(end()) 문법을 응용하여 구현해 보았다. 또한 최종 피로도 계산 시 오버플로우 방지를 위해 long long 자료형을 사용해야 한다는 점을 배웠다.

---

❓ 문제 분석

• 목표: 주어진 $N$ 시간 동안 일을 분배하여 남은 작업량의 제곱의 합 (야근 피로도)을 최소화하는 값을 구해야 한다.
• 제약 조건: $N$은 최대 1,000,000, works 배열 길이는 최대 20,000이다. 총 시간 복잡도는 $O(N \log k)$ 정도가 적절하다. ($k$는 $\text{works}$ 배열의 길이)
• 핵심 키워드: "최소화", "제곱하여 더한 값" $\rightarrow$ 그리디(Greedy) 알고리즘을 고려해야 한다.

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

처음에는 모든 작업을 마친 후 남은 $\text{works}$ 배열을 순회하며 $\sum w_i^2$를 계산하려 했으나, $N$ 시간을 배분하는 모든 경우의 수를 따지는 것은 시간 복잡도가 너무 높아 기각했다.

2. 최종 해결책 (Solution)

야근 피로도($\sum w_i^2$)를 최소화하려면, 작업량 $w_i$가 큰 쪽을 줄여야 피로도 감소 효과가 가장 크다. (예: $5^2 \rightarrow 4^2$는 9 감소, $1^2 \rightarrow 0^2$는 1 감소)

따라서 항상 남아있는 작업량 중 가장 큰 값을 찾아 1 감소시키는 그리디 전략이 최적의 해를 보장한다.

• 자료구조 선택 (priority_queue vs multiset):
  • 보통 최댓값만 필요한 경우 std::priority_queue가 속도와 메모리 면에서 더 효율적이다.
  • 하지만 이번에는 지난 포스트([DAY78])에서 익힌 std::multiset의 반복자 활용법(rbegin, prev)을 실전에 적용해보고자 multiset을 선택했다. 시간 복잡도는 $O(N \log k)$로 동일하여 통과에 무리가 없다.
• 알고리즘 흐름:
  1. works 총합 $\le N$이면 0 반환.
  2. multiset에 작업량 저장.
  3. $N$번 반복: 최댓값(*rbegin())을 찾아 제거하고, 1 감소시켜 다시 삽입.
  4. 남은 원소들의 제곱의 합을 long long으로 반환.

---

💻 코드 구현

#include <string>
#include <vector>
#include <set>

using namespace std;

long long solution(int n, vector<int> works) {
    // 총 작업량 계산 및 예외 처리
    long long total_work = 0;
    for (int work : works) {
        total_work += work;
    }

    if (total_work <= n) {
        return 0; // 모든 작업을 끝낼 수 있음
    }

    // multiset 초기화
    multiset<int> work_set(works.begin(), works.end());

    // 그리디 반복 (N시간 동안 작업)
    for (int i = 0; i < n; ++i) {
        // rbegin()은 오름차순 정렬된 set의 가장 큰 값을 가리킨다.
        int w_max = *work_set.rbegin();
        
        if (w_max == 0) break; 
        
        // 가장 큰 원소 제거 (rbegin() 위치의 반복자를 얻기 위해 prev(end()) 사용)
        work_set.erase(prev(work_set.end())); 
        
        // 1 감소시킨 후 다시 삽입
        work_set.insert(w_max - 1);
    }

    // 최종 피로도 계산
    long long answer = 0;
    for (int work : work_set) {
        // 제곱 연산 시 int 범위를 넘을 수 있으므로 long long 필수
        answer += (long long)work * work;
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 일부 테스트 케이스에서 오답 발생.
• 원인: works의 원소 최대값은 50,000이다. 이를 제곱하면 약 25억이 되어 int 표현 범위(약 21억)를 초과하는 오버플로우가 발생했다.
• 해결: answer 변수를 long long으로 선언하고, 계산식에도 명시적 형변환을 적용했다.

---

✅ 오늘의 회고

항목	내용
유형	Greedy (그리디 알고리즘)
체감 난이도	중
복잡도	시간: $O(N \log k)$, 공간: $O(k)$
새로 배운 것	1. 그리디 증명: 피로도 제곱의 합 최소화는 항상 '최댓값'을 줄이는 것이 최적이다. 2. 지식 응용: 지난번 배운 std::multiset과 prev(end())를 활용해 문제를 해결했다. 3. 자료형 주의: 제곱 연산은 오버플로우 위험이 크므로 long long 사용을 습관화하자.

---