2022.02.26

백준 14501 퇴사

# 14501 퇴사

N = int(input())
T = []
P = []

# 날짜와 금액을 나눠 사용하기 위해 두 리스트에 나눠 저장한다.
for i in range(N):
    a,b = map(int, input().split())
    T.append(a)
    P.append(b)

# result에는 각 날짜로 얻을 수 있는 가장 큰 금액을 저장한다.
result = []
for i in range(N):
    # 현재 날짜와 수행해야 하는 일수를 더해 퇴사날보다 늦으면 0 아니면 P의 값을 저장
    if i + T[i] <= N:
        result.append(P[i])
    else:
        result.append(0)

# 현재 날짜의 수행에 필요한 일수 이후의 날짜이면서 result의 값이 0이 아닌경우
# 얻을 수 있는 최대의 값을 구해준다.
for i in range(N):
    num = i+T[i]
    for j in range(num,N):
        if result[j] != 0:
            result[j] = max(result[j], result[i] + P[j] )

        
print(max(result))