[python] 백준 14501번 퇴사

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

14501번: 퇴사

 

 

 

 

💻 코드

 

import sys

input = sys.stdin.readline

n = int(input())
t_list = []
p_list = []
dp = [0] * (n + 1)

for _ in range(n):
    t, p = map(int, input().split())
    t_list.append(t)
    p_list.append(p)

for i in range(n - 1, - 1, -1):
    if t_list[i] + i > n:
        dp[i] = dp[i + 1]
    else:
        dp[i] = max(p_list[i] + dp[i + t_list[i]], dp[i + 1])
        # (해당 일자에 상담을 하였을 때의 금액 + 해당 일자의 상담기간이 끝난 다음날에 쌓여있는 금액)과
        # (해당 일자에 상담을 하지 않을 경우 쌓여있는 금액) 비교

print(dp[0])

 

 

 

📝 풀이

 

이 문제는 프루트포스 알고리즘 + 다이나믹 프로그래밍 문제로 모든 것을 탐색하면서도 한 번 계산했던 값들은 저장하여 다시 재사용할 수 있도록 코드를 짜야한다.

 

 

 

먼저 t(상담기간)와 p(금액)은 반복문을 통해 인덱스로 접근하여 값들을 서로 비교하면서 최대 이익을 찾아내야 하므로 리스트를 만들어준다. 그리고 한 번 계산했던 값들을 저장하기 위해서 0으로 이루어진 dp 리스트를 n + 1개만큼 만든다. 

 

 

t_list = []
p_list = []
dp = [0] * (n + 1)

for _ in range(n):
    t, p = map(int, input().split())
    t_list.append(t)
    p_list.append(p)

 

 

 

 

 

 

다음은 반복문을 통해 리스트에 접근하여 서로 값을 비교하여 최대 이익을 찾아내야하는데 이때 순차적으로 탐색하는 것보다 거꾸로 탐색하는 것이 더 편리한 방법이었다. 그 이유는 상담 기간 동안에는 다른 상담을 할 수 없기 때문에 해당 일자+상담기간 이후에 얻을 수 있는 이익을 고려해야 하기 때문이다. 즉, 해당 일자 이후와 비교해야 하기 때문에 거꾸로 탐색을 하여 이미 계산되어있는 값들을 이용하는 것이 더 효율적이다. 

 

 

 

 

 

 

if t_list[i] + i > n:
    dp[i] = dp[i + 1]

 

이 if문은 상담기간이 퇴사일을 넘길 경우에는 최대 이익을 얻을 수 있는 금액에 포함시키지 않도록 하기 위한 것이다.

 

 

 

 

 

 

else:
    dp[i] = max(p_list[i] + dp[i + t_list[i]], dp[i + 1])

 

그렇지 않다면, (해당 일자에 상담을 하였을 때의 금액 + 해당 일자의 상담기간이 끝난 다음날에 쌓여있는 금액)과  (해당 일자에 상담을 하지 않을 경우 쌓여있는 금액)을 비교하여 더 큰 것이 최대 이익을 얻을 수 있게 된다. 최종적으로 dp[0]이 되면 최대 이익 금액이 나온다.

 

 

 

 

 

※ 참고

https://gudwns1243.tistory.com/58