[파이썬(python)] 백준 14501번 퇴사

 

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

14501번: 퇴사

 

음.. 다이나믹 프로그래밍인데 삽질을 좀 했다.

일단 내 코드부터 올려본다.

n = int(input())
tp = []
#이차원 배열로 삽입
for _ in range(n):
    t,p = map(int, input().split())
    tp.append([t,p])

result = [0] * n

count = 1
if tp[0][0] > count:
    result[0] = 0
else:
    result[0] = tp[0][1]

for i in range(1, n):
    count += 1
    available = []
    for j in range(i+1):
        if tp[j][0] <= count :
            available.append(tp[j][1])
    
    if len(available) == 0:
        result[i] = result[i-1]
    else:
        count = 1
        result[i] = result[i-1] + max(available)

print(result)

 

정답 코드. 

일단 나는 앞에서부터 최대 수익을 구하려고 했었는데, 이문제의 경우 뒤에서부터 거꾸로 최대 수익을 구해야한다.

앞에서부터 최대 수익을 구하면서 날짜를 늘리다보면 어느 순간 불가능해서 카운트하지 않았던 상담이 가능해지기 때문에, 다시 앞으로 돌아가서 최대 수익을 또 계산해야하는 아주 복잡한 문제가 생긴다.

 

 

따라서 뒤에서부터 거꾸로 수익을 계산하면서 max값을 구해야한다.

 

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

max_value = 0
for i in range(n-1, -1, -1):
    #dp[i] 계산
    time = t[i] + i
    if time <= n:
        dp[i] = max(p[i]+dp[time], max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value

print(max_value)