14501번 파이썬

이 문제는 처음부터 n번째까지 반복해서 문제를 풀었다.

문제의 원리는 예를 들어 설명하는게 이해가 빠를 것 같다.

ex) 1일의 경우 3일이 걸리는 상담이 있는데

코드로 쓰면 num이 1인 경우이고 상담이 완료되는건 idx값이 3이되는 경우이다.

3일차의 최대로 받을 수 있는 금액이 1일차에 3일 상담을 진행해서 받을 수 있는 금액보다 작으면

그 idx에 num-1일까지 받을 수 있었던(1일차 전에 받았던 최대금액) 최대금액에 1일부터 시작해서 받을 수 있는 금액을 더해서 넣어준다.

그리고 마지막으로 p[num]=max를 해준 이유는

idx값이 모든 일 수가 될 수 없는 경우가 있기 때문에 (idx가 3,6,7인 경우 4,5,2,1값은 0이 됨)

현재 값과 전날까지 받았던 최대 금액과 비교해서 더 큰값을 p[num]에 저장해주었다.

import sys
input = sys.stdin.readline
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
p = [0 for _ in range(n+1)]
if ary[0][0]==1:
  p[1]=ary[0][1]
for num in range(1,n+1):
  idx = num+ary[num-1][0]-1
  if idx < n+1:
    if p[idx] < p[num-1]+ary[num-1][1]:
      p[idx]=p[num-1]+ary[num-1][1]
  p[num]=max(p[num],p[num-1])
print(max(p))