[백준 13904번] 과제 (java)
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
그리디 문제이다.
N일째부터 1일째까지 거꾸로 돌면서, n일째에 할 수 있는 과제들 중 가장 점수가 큰 과제를 처리한다.
먼저, 6일째 처리할 수 있는 과제는 5점짜리 과제 하나이다. 따라서 5점짜리 과제를 한다.
sum = 5
그 다음 5일째 처리할 수 있는 과제는 하나도 없다. 이미 5점짜리 과제를 해결했기 때문이다.
4일째에 처리할 수 있는 과제는 10점짜리, 40점짜리, 60점짜리가 있다.
이 중에서 가장 큰 점수를 가지는 과제는 60점짜리 과제이다. 따라서 4일째에는 60점짜리 과제를 처리한다.
sum = 65
3일째에 처리할 수 있는 과제는 10점짜리, 30점짜리, 40점짜리가 있다.
이 중에서 가장 점수가 큰 과제는 40점이므로 3일째 되는 날에는 40점짜리 과제를 처리한다.
sum = 105
2일째에 할 수 있는 과제는 10점짜리, 30점짜리, 50점짜리가 있다.
이 중에서 가장 점수가 큰 과제는 50점짜리이다. 따라서 2일째에는 50점짜리 과제를 처리한다.
sum = 155
마지막으로 1일째 되는 날, 할 수 있는 과제는 10점짜리, 20점짜리, 30점짜리가 있다.
이 중에서 가장 점수가 큰 과제는 30점이므로, 1일째에는 30점짜리 과제를 처리한다.
sum = 185
따라서, 과제는 1일째에 30점, 2일째에 50점, 3일째에 40점, 4일째에 60점, 6일째에 5점짜리를 처리해서
총 185점을 얻을 수 있다.
전체 코드 :