[백준 Python] 14501번 퇴사 (DP)

14501번 퇴사 (DP)

1. 문제

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

 

N일 동안 상담 일정을 받았고, 각 날짜마다 상담을 진행하면 걸리는 시간과 받을 수 있는 금액이 주어진다.

• 퇴사 전까지 최대한 많은 상담을 수행하여 최대 수익을 얻고자 한다.
• 단, 상담은 중복되게 진행할 수 없으며, 퇴사일 이후까지 걸리는 상담도 진행할 수 없다.

 

입력

• 첫째 줄에 N (1 ≤ N ≤ 15)
• 둘째 줄부터 N개의 줄에 걸쳐, 각 날에 대한 상담 기간 T와 수익 P가 주어진다.

출력

• 최대 수익을 출력한다.

---

문제 접근 방법

• 수익을 최대화하는 문제이므로, 완전탐색 or DP를 고려
• "오늘 상담을 한다 vs 하지 않는다" 두 가지 선택지를 모든 날에 대해 고려해야 하므로 브루트포스 기반의 DP가 적절함
• 상담을 하면 i + T일에 다음 선택 가능, 즉 상태 전이 시 다음 인덱스는 유동적
• ⭐️ 각 날짜를 기준으로 최대 수익을 저장하는 1차원 DP 배열 사용 ⭐️

 

---

2. 풀이 과정

🔍 문제 분석

• i번째 날에 상담을 할 수 있는 경우:
  • i + T[i] ≤ N 이어야 함 (퇴사일 전까지 완료)
  • 그때 수익은 P[i]이며, 해당 상담 이후부터 다음 상담을 진행 가능
• i번째 날에 상담을 하지 않는 경우:
  • 이전까지의 수익을 다음 날로 이어감

 

DP 배열 구조

• dp[i]: i일까지 얻을 수 있는 최대 수익
• 초기값은 모두 0으로 설정

 

알고리즘 핵심 로직

1. for i in range(n)로 날짜를 순회하면서:
   • 상담을 할 수 있다면, dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i])
   • 상담을 하지 않더라도, dp[i + 1] = max(dp[i + 1], dp[i])
2. dp[n]에는 퇴사일까지 누적된 최대 수익이 저장됨

 

---

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
schedule = [list(map(int, input().split())) for _ in range(n)]

# dp[i] = i일까지의 최대 수익
dp = [0] * (n + 1)

for i in range(n):
    t, p = schedule[i]

    # 상담을 할 수 있는 경우
    if i + t <= n:
        dp[i + t] = max(dp[i + t], dp[i] + p)

    # 상담을 하지 않는 경우 (그대로 수익 유지)
    dp[i + 1] = max(dp[i + 1], dp[i])

print(dp[n])

 

 

✅ 최적화 포인트

• dp[i] → i일까지 최대 수익을 저장하여, 상담 여부 결정에 사용
• 불필요한 중복 연산 없이 한 방향으로만 순회 (i는 오직 증가)
• 배열 복사 없이 상태 갱신 → 공간 효율성도 좋음

✅ 시간 복잡도

• O(N): 단일 for 루프에서 최대 N번 상태 갱신
• N이 최대 15이므로 시간 여유 충분

---

4. 결과

이 문제의 핵심은 "상담을 할 수 있는지 판단하고, 한다면 그 다음 날짜로 점프하는 방식"이었고,
이를 DP 배열로 관리하여 최적의 수익 경로를 빠르게 구하는 것이 중요했다.