백준 13904번 - 과제 (C++ / Greedy 알고리즘)

https://www.acmicpc.net/problem/13904

 

문제를 접했을 때, 남은 일수를 먼저 할 것인가, 가장 많이 점수를 주는 과제를 수행할 것인지 잘 생각해야하는 문제이다.

 

가장 많은 점수를 주는 과제는 반드시 처리되어야 하지만, 최대한 나중에 밀어두고 처리해야한다. 왜냐하면 

 

10 1000

5 100

1 999

 

이라하자, 그렇다면 가장 많이 주는 과제는 10일이나 남았지만 먼저 처리해버리면 999를 주는 과제를 처리할 수 없다. 그러므로 

 

TASK[DAYS] = DAY 일에 처리할 과제의 점수

 

가 들어있도록 하는 구현 방법을 사용해야한다.

 

이것을 떠올리기가 쉽지 않아 난이도가 있다. 보통 그리디 문제라하면 어떤 answer를 갱신하는 식으로 처리하기 때문이다.

 

그래서 그리디와 자주 함꼐하는 정렬을 할 때, 가장 점수를 많이 주는 대로 정렬하고 점수가 같으면 남을 일수가 많은 순으로 정렬된다.

 

그리고 배열에 넣을 때 만약 

 

10 1000

10 999

10 500 

 

이면,

 

TASK[10] = 1000 이 들어가고, 이후 10 999를 검사할 때 TASK[10] 을 봤을 때 숫자가 있으면 -1 하면서 먼저 처리하도록 한다.

이미 점수를 많이 주는대로 정렬했기 때문에 최적의 해임이 보장된다. 이 문제는 아이디어를 확실히 구현하는 코딩 능력이 중요한 문제였다. 어렵다..

 

그래서 TASK[9] = 999

TASK[8] = 500 이 된다.

 

코드로 구현하면 다음과 같다.

 

#include <iostream>
#include <algorithm>

using namespace std;

vector<pair<int, int>> works;

bool comp(pair<int, int>& a, pair<int, int>& b){
    if(a.second != b.second) return a.second > b.second;
    else return a.first < b.first;
}

int task[1001];

int main(){
    int N; cin >> N;

    for(int i = 0; i < N; i++){
        int a, b; cin >> a >> b;

        works.push_back({a, b});
    }

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

    int answer = 0;

    for(int i = 0; i < works.size(); i++){
        int days = works[i].first;
        int work = works[i].second;

        for(int j = days; j > 0; j--){
            if(task[j] == 0) {
                task[j] = work;
                answer += work;
                break;
            }
        }
    }

    cout << answer << '\n';
}