[백준][DP] 15486. 퇴사 2

15486. 퇴사 2

 

• 내 풀이
  • top-down 방식으로 풀기 전 백트래킹 코드 짜보기
  • 방식은 이런식으로 진행되지만
  • n→ 150만: 시간 터짐

n=int(input())

days=[[0,0] for _ in range(n+1)]
for i in range(1,n+1):
    t,p=map(int,input().split())
    days[i]=[t,p]

answer=0
def dfs(start, price):
    global answer
    if start>n+1:
        return
    if start==n+1:
        answer=max(answer,price)
        return
    
    dfs(start+days[start][0], price+days[start][1])
    dfs(start+1,price)

dfs(1,0)
print(answer)

 

 

• 풀이
  • DP 
    • top-down 방식
    • 재귀제한 안걸면 에러남 -> 제한 + python3 로 돌리기
  • dfs(k)  는 언제 호출해도 동일하다 -> 저장해주기
  • dp≠-1 이면 이미 와본것 → 바로 return
  • start>n 이 넘어도 멈추지말고 가긴 간다
    • 하지만 엄청 큰 손해를 주는 것

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

n=int(input())

days=[[0,0]]+[list(map(int,input().split())) for _ in range(n)]

dp=[-1]*(n+1)
def dfs(start):
    if start>n+1:
        return -float('inf')
    if start==n+1:
        return 0
    if dp[start]!=-1:
        return dp[start]
    
    dp[start]= max(dfs(start+days[start][0])+days[start][1],dfs(start+1))
    return dp[start]
    
print(dfs(1))