[백준] 14501번 퇴사, Python

https://www.acmicpc.net/problem/14501

dp 개념을 입문하기에 참 적합한 문제 같다. 일단 점화식을 잘 세우는 것 부터가 문제였다...

d라는 리스트를 활용해 N일까지 벌 수 있는 최대수익을 저장하도록 했는데,

d[i]는 d[i-1]과 d[i] 중 더 큰 값, 즉 max(d[i-1],d[i])로 설정한다.

x를 상담에 걸리는 날짜라 한다면
d[i+x] 는 d[i-1]에 i일에서 Ti일 후 수익을 더한 값과 d[i+x]중 더 큰 값,
즉 max(d[i-1]+i일에서 Ti일 후 수익,d[i+x]) 이다.

그래서 첫 코드는

import sys
input=sys.stdin.readline
n=int(input())
#n일까지 벌 수 있는 최대수익을 저장,
d=[0]*15
tplist=[[0,0]]
for _ in range(n):
  t,p=map(int,input().split())
  tplist.append([t,p])

for i in range(1,n+1):
  x=tplist[i][0]-1
  d[i]=max(d[i-1],d[i])
  d[i+x] = max(d[i-1]+tplist[i][1],d[i+x])
  
print(d[n])

이었는데 문제 예시는 모두 통과했지만 런타임으로 인덱스 에러가 났다.

알고보니

15
1 1
2 2
3 3
4 4
5 5
1 1
2 2
3 3
4 4
5 5
1 1
2 2
3 3
4 4
5 5

의 경우처럼 마지막 날짜(n)에서 상담에 걸리는 날짜(Tn)이 최댓값인 5일 경우 그 뒷 값을 참조할 수 없어 에러가 나는 것이었다.

그러니까 나는 n의 범위만 고려해서 dp테이블의 길이를 15로 설정했는데, 여기에 T의 최대 범위인 5 까지 더해서 dp테이블의 길이를 20이상으로 맞춰야 하는 것이었다.

따라서 dp테이블의 길이를 20으로 설정한

import sys
input=sys.stdin.readline
n=int(input())
#n일까지 벌 수 있는 최대수익을 저장,
d=[0]*20
tplist=[[0,0]]
for _ in range(n):
  t,p=map(int,input().split())
  tplist.append([t,p])

for i in range(1,n+1):
  x=tplist[i][0]-1
  d[i]=max(d[i-1],d[i])
  d[i+x] = max(d[i-1]+tplist[i][1],d[i+x])
  
print(d[n])

으로 문제를 풀었더니 정답이 떴다.