[DP] 퇴 사

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 퇴사를 앞두고 그 전까지 상담을 많이 해서 한탕 벌고자 하는데, 최대로 벌 수 있는 경우는 무엇인가?

2. 접근 방식

- 마지막 날에 상담은 절대 할 수 없다. 그렇다면 마지막 날부터 계산하면 되지 않을까?

- DP[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대이익
> dp[i] = max(p[i] + dp[t[i]+i], max_value)

3. 코드

n = int(input())
t_ls = [] # 상담에 걸리는 시간
p_ls = [] # 상담 완료시 받을 수 있는 금액
for _ in range(n):
    t, p = map(int, input().split())
    t_ls.append(t)
    p_ls.append(p)
    
max_value = 0
dp = [0]*(n+1)
for i in range(n-1, -1, -1):
    time = t_ls[i]+ i # 상담 시간을 제시 
    if time <= n: # 점화식에 맞게 현재까지 최고 이익 계산
        dp[i] = max(p_ls[i] + dp[time], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value
print(max_value)

4. 코멘트

- 점화식을 세우기 쉽지 않았지만, 어떤 원리인지 이해할 수 있었다. 
- 뒤에서부터 하나씩 채워가면서 앞으로 가는 원리라고 이해하면 편해보인다.

- time = t_ls[i] + i부분을 이해하는데 시간이 좀 걸렸었다. 근데 생각해보면 time이 남은 시간을 초과하게 되면은 해당 원소는 볼 필요가 없다.