[백준] 14501 퇴사

문제출처] https://www.acmicpc.net/problem/14501

14501번: 퇴사

---

문제요약

다이나믹 프로그래밍을 통하여 문제 풀이. 

풀이

dp 배열에 테이블의 점수를 다이나믹 프로그램을 통하여 담으면 된다. dp는 인덱스가 하나 증가할 때마다 최대값을 담아댜 된다.

---

소스코드는 Python 3으로 작성되었습니다.

n = int(input())
table = [[0,0] for i in range(20)] 
dp =[0]*20

for i in range(1,n+1):
  table[i][0], table[i][1] = [int(a) for a in input().split()]

for i in range(1, n + 1) :
  if i + table[i][0] > n + 1 :
    pass
  else:
    dp[i + table[i][0]] = max(dp[i + table[i][0]],table[i][1] + dp[i])
  dp[i + 1] = max(dp[i + 1], dp[i])

print(max(dp))