[백준] 14501번 : 퇴사 (Python3)

예제 입력 1

7

3 10

5 20

1 10

1 20

2 15

4 40

2 200

예제 출력 1

45

예제 입력 2

10

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

예제 출력 2

55

예제 입력 3

10

5 10

5 9

5 8

5 7

5 6

5 10

5 9

5 8

5 7

5 6

예제 출력 3

20

예제 입력 4

10

5 50

4 40

3 30

2 20

1 10

1 10

2 20

3 30

4 40

5 50

예제 출력 4

90

 

풀이 #1

N=int(input())
t, p=[0]*N, [0]*N
for i in range(N):
    t[i], p[i]=map(int, input().split())
DP=[0]*25
for i in range(N):
    if DP[i]>DP[i+1]:
        DP[i+1]=DP[i]
    if DP[i+t[i]]<DP[i]+p[i]:
        DP[i+t[i]]=DP[i]+p[i]
print(DP[N])