[boj] 백준 13904 과제 (c++) - 그리디

[문제]

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

 

[풀이]

1. 점수의 최댓값을 얻기위해서는 점수가 높은 과제 순으로 처리해야 한다.

2. 하지만 점수가 높은 과제에 대해서도 바로 수행하는 것이 아니라, 최대한 마감일까지 미뤄서 수행해야 한다.

 

4 60
2 50
4 40
3 30
1 20
4 10
6 5

 

예제로 주어진 입력을 점수가 높은 순으로 정렬하면 위와 같다. 

과제는 최대한 마감일까지 미뤄서 수행해야 하기 때문에 마감일부터 일수를 감소시켜가며 과제를 수행할 수 있는지 확인한다.

예를 들어, 60인 과제는 4일에 수행가능하므로 score[4] = 60, 50인 과제는 2일에 수행가능하므로 socre[2]= 50이다. 그런데 40인 과제를 보면, 이미 4일에 60인 과제를 수행한 상태이므로 4일째에는 수행할 수 없다. 하지만 하루 감소시킨 3일째에는 수행할 수 있으므로 score[3] = 40과 같이 나타낼 수 있다.

이와 같이 점수가 높은 과제부터 수행하되, 최대한 마감일에 맞춰서 수행할 수 있도록 해준다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <tuple>
#define INF 987654321

using namespace std;

int n;
int score[1001]; //해당 마감일에 수행한 과제 점수

bool compare(pair<int, int> v1, pair<int, int> v2){
    if(v1.second > v2.second) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    vector<pair<int, int>> v;

    for(int i=0; i<n; i++){
        //마감일까지 남은 일수, 과제 점수
        int d, w;
        cin >> d >> w;
        v.push_back({d, w});
    }

    sort(v.begin(), v.end(), compare); //점수 내림차 순 정렬

    int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=v[i].first; j>0; j--){
            if(score[j]==0){
                score[j] = v[i].second;
                ans += score[j];
                break;
            }
        }
    }

    cout << ans;
}