백준 15486번 : 퇴사 2 in Python

15486번: 퇴사 2

 

www.acmicpc.net

이 문제는 N+1일째 되는 날 퇴사하기 전에 남은 N일 동안 상담을 하려고 할 때 얻을 수 있는 최대 수익을 구하는 문제이다.

이 문제는 dynamic programming을 이용해 해결을 해야 한다. 전체 N일 중 각 일자에 대해 순회하면서 i번째 일자에 대해 조사한다고 하자. 우선 i-1번째 일자와 i번째 일자에서의 최대 수익 중 더 큰 값을 dp[i]로 한다. 이는 상담을 할 때 최대 수익을 얻기 위해 꼭 상담을 끝내자마자 바로 그 날의 상담을 시작할 필요가 없기 떄문이다.

그 다음 i번째 일자에 있는 상담을 입력으로 받는다. 그러면 i번째 일자에 있는 상담의 소요 시간 T과 현재 일자를 더한 결과가 N+1을 넘지 않을 때, 즉 퇴사일 전까지 할 수 있는 상담인 경우에만 dp[i+T]을 dp[i+T]와 dp[i]에 i번째 일자에 있는 상담으로 얻을 수 있는 수익을 더한 결과 중 더 큰 값으로 한다.

이를 i가 N이 될 때까지 반복하면 dp[N]을 통해 퇴사 전까지 얻을 수 있는 최대 수익을 구할 수 있다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
dp = [0 for _ in range(N+2)]
max_cost = 0
for i in range(1, N+1):
    dp[i] = max(dp[i-1], dp[i])
    T, P = map(int, input().split())
    if i+T <= N+1:
        dp[i+T] = max(dp[i+T], dp[i] + P)
print(max(dp))