[python 파이썬] 백준 15486번 : 퇴사2

DP 좋은 문제 추천

https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C

문제

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

풀이

max_p[i+1] = max ( max_p[i+1], max_p[i]) 이 부분을 추가 안해줘서 계속 헤맸다. 

답 맞는것 같은데 시간 초과가 계속 뜬다.

n = int(input())
t=[0 for _ in range(n)]
p=[0 for _ in range(n)]
max_p=[0 for _ in range(n+1)]
for i in range(n):
 t[i],p[i] = map(int,input().split())

for i in range(n):
 if i + t[i] < n+1:
 max_p[i + t[i]] = max(max_p[i]+p[i], max_p[i + t[i]])
 max_p[i+1] = max(max_p[i+1],max_p[i])
print(max(max_p))

그래서 알아봤더니 

입출력 속도에 있어서 sys.stdin.readline() > raw_input() > input() 순서대로 빠르다고 한다. 그래서 시간 초과가 뜨는것

sys.stdin.readline() 을 쓰려면 import sys 를 꼭 해주어야 한다.

또, 한 라인 입력받을때는 sys.stdin.readline() 을 하는것이 유리하고

여러 라인을 입력받을때는 sys.stdin() 을 사용하는 것이 유리하다고 한다.

그럼 앞으로 이걸 쓰도록 노력해야겠다...

그래서 최종 정답은 이거

import sys
n= int(sys.stdin.readline())
t=[0 for _ in range(n)]
p=[0 for _ in range(n)]
max_p=[0 for _ in range(n+1)]
for i in range(n):
 t[i],p[i] = map(int,sys.stdin.readline().split())

for i in range(n):
 if i + t[i] < n+1:
 max_p[i + t[i]] = max(max_p[i]+p[i], max_p[i + t[i]])
 max_p[i+1] = max(max_p[i+1],max_p[i])
print(max(max_p))