[BOJ] 백준 13904번 : 과제 (JAVA)

문제

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

 

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

 

 

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

 

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

 

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

 

풀이

그리디 알고리즘으로 풀 수 있는 문제였습니다.

 

이러한 마감 기한이 있는 문제는 1일부터 N일까지 순차적으로 각 날짜에는 무슨 과제를 선택해야하는지 고려하기보다는, N일부터 1일까지 거꾸로 날짜를 세는 것이 좋습니다. 그리고 이렇게 하면 문제가 훨씬 간단해집니다.

 

문제의 예시를 이용하여 위 풀이를 적용해 보겠습니다.

 

 

7

4 60

4 40

1 20

2 50

3 30

4 10

6 5

 

 

이것들을 굳이 정렬할 필요도 없습니다. 과제 마감 기한 중 가장 긴 날짜가 6일이기때문에 6일부터 1일까지 거꾸로 날짜를 세 봅시다.

 

 

먼저, 6일 째는 점수 5짜리 과제밖에 수행할 수 없습니다. 나머지 과제는 모두 마감되었기 때문이죠.

 

5일 째는 수행할 수 있는 과제가 없습니다.

 

4일 째는 60, 40, 10 중에 과제 하나를 고를 수 있는데 당연히 점수가 가장 큰 60짜리 과제를 택해야 합니다.

 

3일 째는 40, 30, 10 중에 과제 하나를 고를 수 있는데, 점수가 가장 큰 40짜리 과제를 택해야 합니다.

 

2일 째는 마찬가지로 50, 30, 10 중에 50을 골라야 합니다.

 

마지막으로 1일 째는 30, 20, 10 중에 30을 골라야 합니다.

 

따라서, 5 + 60 + 40 + 50 + 30 = 185로 힌트에 나와있는 정답과 일치하는 것을 알 수 있습니다.

 

 

이렇게 날짜를 거꾸로 세되, 이미 수행한 과제는 리스트에서 지워주어야 합니다. 시간복잡도는 O(N²)이지만, N이 고작 1,000이므로 충분히 시간 안에 돌아간다는 것을 알 수 있습니다.

 

 

소스코드

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.