14501 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

 

유명한 DP문제로 점화식을 세우는 것이 힘든 문제다.

 

간단히 말해서, 오늘을 근무할것인가, 말것인가를 선택하는 문제로 바꿔 생각할 수 있으며,

 

dp[i]는 i번째날 얻을 수 있는 최대 소득으로 정의한 후 접근하면 풀리는 문제이다.

 

물론 나도 그렇게 능숙하진않아서 오래걸렸지만 스스로 풀었다는점에서 의의가 있다고 생각한다. (KTX에서 풀었음 ㄷ)

 

import sys
input = sys.stdin.readline

n = int(input())
info = [ [] ] # index 1부터 시작하기 용
for _ in range(n):
  t, p = map(int, input().split(" "))
  info.append((t,p))

# dp[i] 는 i번째 일짜에 얻을 수 있는 최대 소득
dp = [0] * (n+1)

# solve(d, t) 는 d번째날 t소득인 상태로 진입한다는 뜻
def solve(curr_day, total):
  global n,info,dp

  # n+1인경우 한번 더 체크
  if(curr_day + info[curr_day][0] == n+1):
    if( dp[curr_day] < total+info[curr_day][1] ):
      dp[curr_day] = total+info[curr_day][1]

  # 현재 날짜 근무
  if( curr_day + info[curr_day][0] <= n ):
    if( dp[curr_day] < total+info[curr_day][1] ):
      dp[curr_day] = total+info[curr_day][1]
      solve(curr_day + info[curr_day][0], dp[curr_day])

  # 현재 날짜 스킵
  if( curr_day + 1 <= n ):
    solve(curr_day + 1, total)

solve(1, dp[1])

print(max(dp))