문제

SW 역량 테스트는 총 T분동안 진행되며 N개의 문제가 나온다. 대회가 진행되는 동안 아무 때나 소스 코드를 제출할 수 있다.

i번 문제를 t분에 맞춘 경우에는 Mi-t*Pi 점을 받게 된다. 이 테스트에 응시한 백준이가 i번 문제를 푸는데 걸리는 시간은 Ri분이다.

백준이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : Greedy, DP

강산님의 글을 참고하여 풀이를 작성하였습니다.

생각해보면, P_i 는 페널티 느낌으로, P_i 가 클 수록 늦게 풀면 완전 손해입니다.

더 나아가 문제풀이가 t 시간 진행 된 후, a, b 두 문제를 풀어 얻는 점수를 생각해보면

1] a 풀고 b 푸는 경우 얻는 점수 :

M_a-(t+R_a)*P_a + M_b-(t+R_a+R_b)*P_b

2] b 풀고 a 푸는 경우 얻는 점수 :

M_b-(t+R_b)*P_b + M_a-(t+R_b+R_a)*P_a

입니다.

a 먼저 푸는게 이득이려면 1] - 2] > 0 이어야 겠죠?

1] - 2] = R_b*P_a - R_a*P_b > 0 이면 a 먼저 푸는게 이득입니다.

즉 R_a/P_a < R_b/R_a 이면 a 먼저 푸는게 이득입니다.

따라서 Greedy 느낌으로 R/P 가 작은거부터 푸는게 이득일겁니다.

과정(1) 의 생각을 구현하는 struct 를 만들고, 이를 sort 해줍니다. (R/P가 작은게 먼저오게)

sort 된 문제들을 차례로 탐색하며 dp 로 푸는 함수를 만듭니다.

'dp[k][t] : k번째 문제, t의 시간 에서 얻을 수 있는 최대 점수' 라고 설정하였습니다.

각 문제를 탐색 할 때

1] 안 풀고 넘기는 경우

2] 풀고 넘기는 경우

2가지 경우가 있겠죠?

안 풀고 넘기면 시간을 안쓰고, 풀고 넘길 경우 시간을 쓰고 점수를 얻겠죠...

문제를 풀 경우는 현재시간 + 문제풀이시간 <= 제한시간 이어야 합니다.