[boj] 퇴사_14501

# 퇴사 https://www.acmicpc.net/problem/14501

time_cost = list()
price_earn = list()
max_val = 0

N = int(input())

dp = [0 for i in range(N+1)]

for _ in range(N):
    T, P = map(int, input().split())
    time_cost.append(T)
    price_earn.append(P)

# dp[i] = i일부터 마지막까지 상담 시 얻을 수 있는 최대 이득
# dp[i] = p[i] + dp[i+t[i]]

# N일부터 1일까지 거꾸로 계산
for i in range(N-1, -1, -1):
    temp = i + time_cost[i]
    if temp <= N:
        dp[i] = max(price_earn[i] + dp[temp], max_val)
        max_val = dp[i]
    else:
        dp[i] = max_val

print(max_val)

이전 삼성 SW 코딩테스트 기출문제라고 한다.

DP를 이용해 푸는 문제인데 반나절 이상을 고민했는데도 도저히 문제를 맞출수가 없어서 해답이란 해답을 모조리 찾아봤다. 심지어 해답도 이해가 잘 안감...(패배감 오지고지리고...)

 

각 날의 상담마다 소요되는 시간 time_cost 리스트와 해당하는 이득인 price_earn 리스트에 값을 저장해 사용한다.

dp는 점화식을 세우는 것과 이전에 계산한 결과를 이용하는 것이 관건인데, 이 문제에서는 " i번째 날부터 상담을 하여 얻을 수 있는 최대의 이득 " 을 dp[i]라 하여 dp리스트에 저장해 사용한다.

 

만약 첫째 날부터 상담을 시작하고 첫째 날 상담의 소요시간이 3일이라면, 4일부터 상담이 가능하므로 'dp[1] = 1일차의 상담 이득 + 4일차부터 얻을수 있는 최대 이득' 이된다. 이를 수식으로 쓰면 dp[1] = dp[time_cost[1]] + price_earn[1]이 된다.

 

또 하나 염두해야 할 점은, 상담이 끝난 이후에 바로 상담을 시작한다고 해서 반드시 최대 이익을 보장하지는 않는다는 점이다.

 

사실 글을 쓰면서도 잘 설명하기가 너무 어렵다고 느껴진다. 이후에 반추하며 좀 더 깔끔하게 설명할 수 있도록 공부할 예정이다.