문제

🔍My Approach

• 해당 문제는 정해진 기간에 백준이가 얻을 수 있는 최대 수익을 구하는 문제이므로, dp를 사용하며 dp에는 해당 날부터 퇴사일까지 일을 했을 때 받을 수 있는 최대 수익을 저장한다.
• 퇴사 전 날 가장 dp가 적고, 1일차가 가장 dp가 크므로, dp는 역순으로 진행한다.
• dp의 시작 조건은 dp[N+2] = 0, **t[N] == 1이면 dp[N+1] = p[N]**으로 설정하고 t[N] ≠ 1이면 dp[N+1]= 0으로 설정한다.
  • 마지막날 상담이 하루가 걸리면 마지막날에 상담을 진행하며 수익을 얻을 수 있고, 마지막날 상담이 하루를 초과하면 상담을 진행할 수 없기 때문에 최대수익은 0이기 때문이다.
• 점화식은
  • 현재일 + 현재일에 예약된 상담일수 ≤ 퇴사일일때는 상담이 가능하므로 max(다음날의 최대수익, 현재일의 상담 예약 수익 + 상담이 끝나는 날의 최대 수익)

🚩My Submission

N = int(input())

T = [0]
P = [0]
dp = [0] * (N + 2)

for _ in range(N):
    arr = input().split()
    T.append(int(arr[0]))
    P.append(int(arr[1]))

#dp 시작 조건
if T[N] == 1:
    dp[N + 1] = 0
    dp[N] = P[N]
else:
    dp[N + 1] = 0
    dp[N] = 0

for i in range(N - 1, 0, -1):
    if i + T[i] <= N + 1:
        dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])
    else:
        dp[i] = dp[i + 1]

print(dp[1])

💡TIL

1. 점화식 조건에서 i+T[i] ≤ N+1이 있고 이것은 현재일 + 현재일에 예약된 상담일수가 퇴사일을 넘기지 않아서 상담이 가능하다는 것이다. 이때 퇴사일(N+1)에 대한 dp를 시작조건에서 정해놓지 않아서 i+T[i]가 N+1일때, indexError가 발생했다.
2. 배열을 처리할 때 어떤 것은 1부터 시작하고 어떤 것은 0부터 시작해서 혼란이 있었다. index를 1 기준으로 처리해야 헷갈리지 않을 것 같다.