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

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

15486번: 퇴사 2

문제 요약 : 상담일을 하는 백준이는 N+1일 째 되는 날 퇴사를 한다. 남은 N일 동안 최대한 많은 상담을 하려고 한다. 이때 백준이가 얻을 수 있는 이익을 구하여라.

 

예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

45

 

시도 )

보자마자 dp문제라는 느낌이 왔다.

날짜의 개수만큼 dp를 생성해주고, T와 P를(상담걸리는 기간, 금액)받아온다.

 

(현재날짜 + 상담기간)에 해당 날짜의 값과 현재날짜에 금액을 더한 값을 비교하여 더 큰 값을 넣어준다.

그러나, 이 코드만 추가하면 마지막 예제가 풀리지 않았는데, 그 이유는 중간에 값이 갱신되지 않은 값이 존재할 수 있기 때문이다.

그래서 어차피 N만큼 for문을 돌기 때문에 dp[now]에도 값을 갱신해주도록 하였다.

 

어차피 dp[now]를 기준으로 앞의 값들은 전부 지나간 일정이기 때문에 가장 큰 값이 들어가도록 해주었으나, max는 시간복잡도가 O(n)이기 때문에 그런지 시간초과가 떴다.

자신의 값을 갱신해주긴 갱신해주어야하는데.. 이 고민을 오래 한 것 같다.

# 퇴사 2
N = int(input())
dp = list(0 for _ in range(N+1))
for now in range(N):
    T,P = map(int,input().split(' '))
    dp[now] = max(dp[:now+1])
    if now + T < N+1 :
        dp[now+T] = max(dp[now+T],dp[now]+P)

print(max(dp))

 

📌 풀이 )

1. dp를 N+1개 만들어준다.(1일부터 N일까지 사용하기 위함)
   • dp[i]는 i일 일때, 가장 큰 값을 저장한다.
2. N동안 T와 P를 받아온다.
3. 현재 날짜가 가질 수 있는값을 갱신해준다.(지금값과 이전 값 중 큰 값을 저장)
4. 현재 날짜에서 상담을 할 경우, 상담을 끝 마쳤을 때의 값을 갱신해준다.
5. dp[-1]을 출력한다.

앞서 고민했던 갱신 값을 그냥 이전 값과 비교해서 큰 값을 넣어주는 걸로 바꾸었다. 시간초과안뜸!

# 퇴사 2
import sys
input = sys.stdin.readline

N = int(input())
dp = list(0 for _ in range(N+1))

for now in range(N):
    T,P = map(int,input().split(' '))
    
    dp[now+1] = max(dp[now+1],dp[now])    
    if now + T < N+1 :
        dp[now+T] = max(dp[now+T],dp[now]+P)

print(dp[-1])