[백준] No.13904 - 과제 (C++)
문제
https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
풀이
solved.ac 난이도: Gold 3
그리디(탐욕법) 문제이지만 브루트 포스도 이용하여 문제를 해결하였다.
일단 pair<int, int>의 first에 남은 일자를, second에 점수를 저장하고 남은 일자를 기준으로 내림차순 정렬을 하자.
문제의 예제는 아래와 같이 정렬된다.
6 5
4 60
4 40
4 10
3 30
2 50
1 20
기간이 많이 남을 수록 앞쪽으로 정렬되기 때문에 최대 기한인 6일을 기준으로 day_cnt를 하루하루 줄이면서(6->5->4...->1) 진행한다. day_cnt보다 크거나 같은 날짜 중에서 점수가 최대인 과제를 선택하면 점수가 큰 과제를 최대한 미루는 그리디 방식의 구현이 가능하다. 이때 점수가 큰 과제를 최대한 마감 직전까지 미루는 이유는 간단하다.
2 40
1 10
1 20
위와 같은 입력에서 만약 점수가 높은 과제를 먼저 하기 위해 첫날에 40점인 과제를 먼저 해결한다면 20점인 과제는 놓치게 되어 결과적으로는 총점은 낮을 수밖에 없다.
문제의 예제 입력은 아래와 같은 순서로 진행된다.
day_cnt=6일때
6 5 -> 선택! sum = 5
--------- 6 이상만 선택 가능
4 60
4 40
4 10
3 30
2 50
1 20
day_cnt=5
---------- 5 이상이 없음!
4 60
4 40
4 10
3 30
2 50
1 20
day_cnt=4
4 60 -> 선택! sum = 65
4 40
4 10
--------- 4 이상에서 최댓값을 선택
3 30
2 50
1 20
day_cnt=3
4 40 -> 선택! sum = 105
4 10
3 30
--------- 3 이상에서 최댓값을 선택
2 50
1 20
day_cnt=2
4 10
3 30
2 50 -> 선택! sum = 155
--------- 2 이상에서 최댓값을 선택
1 20
day_cnt=1
4 10
3 30 -> 선택! sum = 185
1 20
--------- 1 이상에서 최댓값을 선택
day_cnt이상인 값에서 최댓값을 찾는 코드의 시간 복잡도는 O(N^2)이므로 충분히 시간 안에 탐색 가능하다.
이를 구현하기 위해 최댓값으로 선택된 과제는 더 이상 선택되면 안 된다. 따라서 간단히 선택된 과제의 idx를 selected_idx에 저장해 두고 해당 과제의 점수인 assignment_list[selected_idx].second를 0으로 만들어준다. 이렇게 하면 최댓값으로 다시 선택되는 것은 불가능하다.
본 문제는 점수가 높은 순으로 정렬하여 최대한 미루어 선택하는 더 빠른 풀이와 우선순위 큐를 이용하는 간단한 풀이가 존재하니 참고하면 좋다.
코드