boj15486 퇴사2-dp

dp.. 생각해내는게 어렵다.. ㅇㅅㅇ

각 날짜에서 가능한 최대 이익을 계산.

1. dp 배열을 초기화

2. 뒤에서부터 각 날짜별로 상담을 진행했을 때 얻을 수 있는 최대 이익을 계산. 상담이 끝나는 날이 퇴사일을 넘어가지 않는 경우, 상담을 진행하는 것이 더 이익이 되는지, 아니면 진행하지 않는 것이 더 이익이 되는지를 판단하여 dp 값을 갱신

3. 만약 상담이 끝나는 날이 퇴사일을 넘어가는 경우, 그 날의 상담은 진행할 수 없으므로 이전에 계산한 최대 이익을 그대로 사용

이런 식으로 모든 날짜에 대한 계산을 완료하면, dp[0]에는 첫 날부터 시작하여 얻을 수 있는 최대 이익이 저장

코드

N = int(input())

T, P = [0]*N, [0]*N

dp = [0]*(N+1)  # 동적 프로그래밍 테이블 초기화

for i in range(N):
    T[i], P[i] = map(int, input().split())

for i in range(N-1, -1, -1):  # 뒤에서부터 계산
    if T[i] + i <= N:  # 상담이 끝나는 날이 퇴사일을 넘어가지 않는 경우
        dp[i] = max(P[i] + dp[i + T[i]], dp[i+1])  # 오늘 상담을 선택하는 경우와 선택하지 않는 경우 중 더 큰 경우 선택
    else:  # 상담이 끝나는 날이 퇴사일을 넘어가는 경우
        dp[i] = dp[i+1]  # 오늘 상담을 선택할 수 없음

print(dp[0])  # 첫째 날부터 최대 이익