[백준] 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으로 만들어준다. 이렇게 하면 최댓값으로 다시 선택되는 것은 불가능하다.
본 문제는 점수가 높은 순으로 정렬하여 최대한 미루어 선택하는 더 빠른 풀이와 우선순위 큐를 이용하는 간단한 풀이가 존재하니 참고하면 좋다.
코드
| #include <iostream> | |
| #include<string.h> | |
| #include<algorithm> | |
| #include<vector> | |
| using namespace std; | |
| int main() { | |
| int assignment_num,day,score; | |
| bool pos_assignment[1000]; | |
| vector<pair<int,int>> assignment_list; | |
| cin>>assignment_num; | |
| for(int i=0; i<assignment_num ; ++i){ | |
| cin>>day>>score; | |
| assignment_list.push_back(make_pair(day, score)); | |
| } | |
| sort(assignment_list.begin(), assignment_list.end(),greater()); | |
| memset(pos_assignment, true, sizeof(pos_assignment)); | |
| int pos_assignment_idx = 0; | |
| int sum=0, max_score; | |
| for(int day_cnt = assignment_list[0].first ; day_cnt >=1 ; --day_cnt ){ | |
| //assignment_list[0].first는 가장 기한기 긴 과제의 남은 날짜이다. | |
| while(day_cnt <= assignment_list[pos_assignment_idx].first) | |
| ++pos_assignment_idx; //day_cnt미만이 과제가 나올때까지 ++pos_assignment_idx | |
| max_score = 0; | |
| int selected_idx; | |
| max_score = assignment_list[0].second; | |
| selected_idx =0; | |
| for(int idx=1; idx<pos_assignment_idx ; ++idx){ | |
| if(assignment_list[idx].second > max_score){ | |
| max_score = assignment_list[idx].second; | |
| selected_idx = idx; | |
| } | |
| } | |
| sum += max_score; | |
| assignment_list[selected_idx].second =0; //선택된 과제는 0으로 | |
| } | |
| cout<<sum<<'\n'; | |
| return 0; | |
| } |