[python] 백준 15486 번 : 퇴사2

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

15486번: 퇴사 2

 

1. 코드 구현 

n = int(input())
t = [0]*(n+1)
p = [0]*(n+1)
dp = [0]*(n+2)
for i in range(n):
    t[i+1], p[i+1] = list(map(int, input().split()))

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

 

 

1일부터 n일까지 상담 일정이 있는 경우, n일부터 거꾸로 시작하여 받을 수 있는 최대 금액을 구하는 방식으로 구현하였다. 예를 들어, 상담 일정표가 다음과 같다고 가정하자.

 

7일의 경우 1일만에 끝낼 수 있으므로 7일에 받을 수 있는 금액은 5이다.

그리고 6일에 예정된 상담은 이틀이 걸리므로 6일, 7일안에 일을 해결하면 되므로 상담을 받을 수 있다. 따라서 7일에 받을 수 있는 최대 금액은 30이다. 만약 7일에 받은 상담 금액이 30보다 컸더라면 6일에 상담을 받으면 7일에 상담을 받지 못하니까 7일 상담 금액을 받는게 6일에 받을 수 있는 최대 상담 금액이 된다.

dp[i]를 n일부터 i일까지 받을 수 있는 최대 상담 금액이라고 하자. 그리고나서 이러한 방식으로 dp 값을 구하면 다음과 같이 표가 완성된다.  

 

 

2. 코드 구현 

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

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

print(max(dp))

dp[i]를 1일 부터 n까지 받을 수 있는 최대 상담 금액이라 두었을 때의 코드는 위와 같다.