백준 14501 퇴사

gmlwlswldbs·2021년 9월 21일
0

코딩테스트

목록 보기
33/130
inf = 10**9
n = int(input())
t = [0] * n
p = [0] * n
for i in range(n):
    t[i], p[i] = map(int, input().split())
d = [-1] * n
def go(index):
    if index > n:
        return -inf 
    if index == n:
        return 0
    if d[index] != -1:
        return d[index]
    a = p[index] + go(index + t[index])
    b = go(index + 1)
    d[index] = max(a, b)
    return d[index]

print(go(0))   

재귀함수를 통해 구하고 + sum 대신 메모이제이션을 추가하여 dp로 푼다

0개의 댓글