[n15486] 퇴사 2 in python

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

15486번: 퇴사 2

---

(처음 든 생각)

항상 완탐부터 생각난다....

하지만 딱 떠오르는 생각이 없었다.

 

아무리 생각해봐도 모르겠어서

인터넷 풀이 검색..

 

---

(풀이 : dp)

처음에 input()으로 입력값을 받았는데 시간초과,

sys.stdin.readlin() 사용하니까 통과함!

 

이 문제는 완탐으로 하면 시간초과가 뜬다

연산개수가 150만개라서..!

 

생각해야 하는 부분

1. 해당 날짜에 상담을 할 것인가

2. 상담을 하지 않을 것인가

 

1번과 2번의 값중에 큰 값을 따라가는 방식

 

만약 현재 일수에 t를 더한 값이 n이하일 경우에는 상담이 가능하다.

만약 n보다 큰 값이면, 상담을 하지 못하니까 2번 연산만 수행된다. 

import sys

n = int(sys.stdin.readline().rstrip())

array = [[0, 0] for _ in range(n)]

for i in range(n):
    array[i] = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [0 for _ in range(n + 1)]
term = 0
i = 1

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