[그리디] 과제(13904)(C++)

 

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

13904번: 과제

 

1. 문제 개요

 

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

입력값을 과제의 배점이 높은 순으로 정렬하고 배점이 같다면 늦게 끝나는 순으로 정렬한다.

그 다음 날짜를 저장하는 배열에 끝나는 날짜부터 시작해서 처음 날짜까지 확인하며 넣을 자리가 있다면 넣어준다.

예를 들어서 다음과 같이 정렬된 값이 있다고 하면, 첫번째 값부터 차례대로 배열에 넣어주면 된다.

 

1. 배열의 모든 원소를 0으로 초기화 한다.

1	2	3	4	5
0	0	0	0	0

2. 첫번째 과제부터 비어있는 날짜를 찾아 저장해준다.

이때 비어있는 날짜는 마감일부터 0번째 원소까지 차례로 찾는다. (4, 60) 과제의 경우 배열의 4번째 자리가 비어있으므로 그 자리에 넣어준다. 

1	2	3	4	5
0	0	0	60	0

2. 나머지 과제에 대해서도 똑같이 수행해준다.

두 번째 과제의 경우 (2, 50)이고 두 번째 날이 0(비어있음)이므로 해당 날짜에 마킹해준다. 또 총점에 해당 과제의 점수를 더해준다.

1	2	3	4	5
0	50	0	60	0

 

세 번째 과제의 경우 (4, 40)이고 네 번째 날이 마킹되어있으므로 그 전날인 세 번째 날에 넣어준다.  또 총점에 해당 과제의 점수를 더해준다.

1	2	3	4	5
0	50	40	60	0

네 번째 과제의 경우 (3, 30)이고 세 번째 날과 두 번째 날이 이미 마킹되어있으므로 남는 날인 첫번째 날에 넣어준다.

1	2	3	4	5
30	50	40	60	0

다섯 번째, 여섯 번째 과제의 경우 (1, 20), (4, 10) 이고 1~4까지의 날짜가 이미 모두 마킹되어있으므로 과제를 수행하지 않는다.

1	2	3	4	5
30	50	40	60	0

마지막 과제의 경우 (6,5)이고 여섯 번째 날짜가 비어있으므로 그 날짜에 넣어준다.

 

1	2	3	4	5	6
30	50	40	60	0	5

이렇게 하면 과제 점수의 총합이 185가 된다.

 

 

4. 전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int list[1001];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
    if(p1.second==p2.second)
        return p1.first > p2.first;
    return p1.second > p2.second;
}

int main(void)
{
    int N;
    vector<pair<int, int>> v;
    scanf("%d",&N);
    
    int temp1, temp2;
    for(int i=0;i<N;i++){
        scanf("%d%d",&temp1,&temp2);
        v.push_back({temp1,temp2});
    }
    
    sort(v.begin(),v.end(),cmp);
    
    int sum = 0;
    for(int i=0;i<N;i++){
        for(int j=v[i].first;j>0;j--){
            if(!list[j]) {
                list[j] = 1;
                sum += v[i].second;
                break;
            }
        }
    }
    
    printf("%d",sum);
}