[백준] 14501 퇴사 | 파이썬 | 백트래킹 & DP

14501: 퇴사

DFS(백트래킹) 이용한 풀이

가능한 모든 경우를 탐색하며 최댓값을 찾는 방식

import sys
input = sys.stdin.readline

N = int(input())
T = []
P = []
for _ in range(N):
    t, p = map(int, input().split())
    T.append(t)
    P.append(p)

max_profit = 0  # 최대 수익 저장

def dfs(day, total_profit):
    global max_profit

    # 퇴사일(N+1)이 되면 종료
    if day >= N:
        max_profit = max(max_profit, total_profit)
        return

    # 상담을 진행하는 경우 (퇴사일을 넘지 않는다면)
    if day + T[day] <= N:
        dfs(day + T[day], total_profit + P[day])

    # 상담을 진행하지 않는 경우
    dfs(day + 1, total_profit)

dfs(0, 0)
print(max_profit)

---

dp를 이용한 풀이

dp[N+1] 배열을 만들어서 i일차부터 N일까지 얻을 수 있는 최대 이익을 저장

       # 상담 안 했을 때  vs  상담 선택 
dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])

📍 dp 배열을 N+1 크기로 만드는 이유

dp[i] 계산할 때 dp[i + T[i]] 값 참조하는데, i + T[i] == N 이 될 수도 있음!
이를 방지하기 위해 dp[N] = 0 설정

• dp[0] : 첫날(0일차)부터 N일까지 얻을 수 있는 최대 이익
• dp[N-1] : 마지막 날(N-1일차)부터 N일까지 얻을 수 있는 최대 이익
• dp[N] : 퇴사 이후 0

📍 dp에서 거꾸로(N-1부터 0까지) 가는 이유

dp[i]를 구할 때 첫날부터 (0→N) 진행한다고 해보자

주어진 예제에서 0일차에 상담을 할지 말지를 결정하려고 할 때,
상담을 하면 dp[0] = P[0] + dp[3]
첫번째 상담을 하면 3일동안 상담 못하니까 4일째 상담부터 가능 (dp[3])

그래서 dp[0]을 구하려면, dp[3]이 먼저 계산되어야 한다!!

📍 dp[i] = dp[i+1] ?

상담을 선택 하지 않은 날
👉 “이 날엔 상담을 못하니까, 그냥 다음 날부터의 최댓값을 그대로 가져오자!!”

📒 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
T = []
P = []
dp = [0] * (N + 1)  # dp[i]는 i일차까지의 최대 수익을 저장

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

# 뒤에서부터 거꾸로 DP 계산
for i in range(N - 1, -1, -1):
    if i + T[i] > N:  # 상담이 퇴사일을 넘어가는 경우
        dp[i] = dp[i + 1]
    else:
        # 상담을 선택한 경우 vs 선택하지 않은 경우
        dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]])

print(dp[0])