[백준] 14051 퇴사(Python)

해당 게시글에서는 [백준] 14501 퇴사 문제를 해설하고 Python을 이용하여 풀고자 한다.

🤔 접근법

문제 풀이 방식을 빠르게 알고싶다면 💡문제 풀이 부분 부터 봐주세요 :)

필자는 본인의 힘으로 해당 문제를 풀지 못했다. 따라서 이후에 유사한 문제를 볼 때 기억이 더 잘 나도록 블로깅을 하려고 한다.

14501번 문제는 DP(다이나믹 프로그래밍)에 대한 문제로 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법하는 방식의 알고리즘이다.

현재 바킹독의 알고리즘 문제집을 참고하여 알고리즘 별로 문제를 풀고있기 때문에 이 문제가 DP 문제라는 것을 알고 있었다.

문제를 읽어가며 최대 수익을 내기 위한 방법을 찾으려고 시도했지만 실패했다. 같은 일에 상담을 하더라도 T_i에 저장된 값이 다르면 수익을 얻는 날짜가 다르기 때문이다.

아이디어가 도저히 떠오르지 않자 구글링을 통해 아이디어를 탐색했다.

그 결과 뒤쪽 인덱스부터 접근해야 된다는 것과 i일에 상담을 진행한 경우와 아닌 경우로 나눠 최댓값을 구하면 된다는 것을 알았다.

i일에 상담을 진행할 때의 수익은 i+T_i일에서의 수익에 P_i를 더한 값이며, i일에 상담을 진행하지 않았을 때의 수익은 i+1일에서의 최댓값이다.

즉 i일에서의 최댓값은 상담을 진행할 때, 진행하지 않았을 때 중 더 최댓값을 선택하면 된다.

💡 문제 풀이

위에서의 아이디어를 정리하면 다음과 같다.

✅ i일에서의 최대 수익은 다음 중 큰 값에 해당

• i일에 상담⭕: P[i]+dp[i+T_i]
• i일에 상담❌: dp[i+1]

이를 파이썬 코드로 나타내면 다음과 같다.

if i+T[i]>N+1:
    dp[i] = dp[i+1]
else:
    dp[i] = max(dp[i+1], P[i]+dp[i+T[i]])

이때 주의해야 할 부분은 N일 이후에는 수익을 낼 수 없으므로 이에 대한 예외처리를 해야한다는 것이다.

또 이 부분에 어떤 식을 넣어줄 것인가도 고민해야 한다. 필자는 처음에 continue를 썼다가 해당하는 dp[i]에 모두 0이 저장되는 바람에 else에서 이전 값들이 갱신되지 않는 문제가 발생했다.

📂 코드

위 문제 풀이 방식을 통해 해당 문제를 풀어낸 필자의 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N = int(read().strip())
T, P = [0], [0]
for i in range(1, N+1):
    t, p = map(int, read().split())
    T.append(t)
    P.append(p)

dp = [0]*(N+6) # i번째 일에 상담 시 얻을 수 있는 최대 수익
for i in range(N, 0, -1):
    if i+T[i]>N+1:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], P[i]+dp[i+T[i]])
print(dp[1])