백준 14501번 : 퇴사 (Python)

문제 : www.acmicpc.net/problem/14501

14501번: 퇴사

 

풀이

리스트 A에 입력받은 값을 저장한다. 시작 날짜 인덱스에 [끝나는 날짜, 금액] 을 저장하도록 했다.

dp에 수익을 저장하도록 한다.

이중 포문중 바깥포문은 A 리스트를 인덱스 i로 방문한다.

안 포문은 i부터 끝까지 dp를 방문하며 i일 현재 수익 + i상담의 수익이 i일 상담이 끝나는 날의 현재 수익보다 크다면 큰 값으로 변경한다.

가장 큰 수익을 출력한다.

 

n = int(input())

A = [[]]
for i in range(1,n+1):
    A.append(list(map(int, input().split(" "))))
    A[i][0] += i
    
dp = [0 for _ in range(n+2)]

for i in range(1,n+1):
    for j in range(A[i][0],n+2):
        if dp[j] < dp[i] + A[i][1]:
            dp[j] = dp[i] + A[i][1]

print(max(dp))