백준 13904 - 과제

문제

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

13904번: 과제

 

풀이

점수가 최대가 되야하므로 점수를 내림차순으로 정렬해서 선택한다. 그리고 마감일이 오래 되는 과제는 당장 해결 할 필요가 없으므로 미룰 수 있을 만큼 미뤄야 한다. 이를 위해 배열 due를 만들어서 이 배열에다 선택 된 과제들만 저장한다.

 

1. index에 마감일을 저장

2. 마감일이 중복이 아니면 (due[index] == 0) 점수 저장 (마감일까지 과제를 최대한 미룸)

3. 마감일이 중복되면 (due[index] != 0) --index를 하면서 빈 공간을 찾아서 저장, 없으면 그 점수는 포기 (--인 이유는 마감일을 증가 할 수 없기 때문)

4. 1번, 2번, 3번 반복

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int d, w;
pair<int, int> arr[1000];
int due[1001];
int result;
 
class cmp
{
public:
    bool operator()(pair<int, int> &a, pair<int, int> &b)
    {
        return a.second > b.second ? true : false;
    }
};
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 0; i < N; i++)    cin >> arr[i].first >> arr[i].second;
    
    // 점수 내림차순 정렬
    sort(arr, arr + N, cmp());
 
    // 가장 높은 점수부터 연기할 수 있을 만큼 연기함, 만약 불가능하면 그 점수는 포기
    for (int i = 0; i < N; i++)
    {
        int index = arr[i].first;
        if (!due[index]) due[index] = arr[i].second;
        else
        {
            while (due[--index]);
            if (index != 0) due[index] = arr[i].second;
        }
    }
 
    for (int i = 1; i < 1001; i++) result += due[i];
    cout << result;
 
    return 0;
}