[백준] No.13904 - 과제 (C++)

문제

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

13904번: 과제

 

풀이

 

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으로 만들어준다. 이렇게 하면 최댓값으로 다시 선택되는 것은 불가능하다.

 

 

본 문제는 점수가 높은 순으로 정렬하여 최대한 미루어 선택하는 더 빠른 풀이와 우선순위 큐를 이용하는 간단한 풀이가 존재하니 참고하면 좋다.

 

코드