[코딩테스트, 더 이상 미룰 수 없다] BOJ 14501 - 코드를 외워둘 만한 대표적 DP 문제

14501은 DP를 공부할 때 꼭 한 번 정리해둘 만한 문제였다.
코드 길이도 길지 않고, 상태 정의와 점화식이 분명해서 기본기를 익히기에 좋다.
앞으로 비슷한 유형의 문제를 만났을 때 떠올리기 쉬운 형태이기도 하다.

왜 기억해둘 만한 문제인가

이 문제는 매 날짜마다 선택이 하나씩 주어진다.

• 오늘 상담을 한다
• 오늘 상담을 하지 않는다

그리고 이 두 선택 중 더 좋은 결과를 고르면 된다.

문제 구조가 단순해서 DP의 핵심이 잘 보인다.
현재 위치에서 어떤 선택을 할 수 있는지, 그 선택이 다음 상태에 어떤 영향을 주는지를 그대로 식으로 만들 수 있다.

이런 형태는 다른 문제에서도 자주 나온다.

• 어떤 일을 수행할지 말지 고르는 경우
• 특정 구간을 사용할지 건너뛸지 정하는 경우
• 현재 선택 때문에 다음에 가능한 날짜나 위치가 달라지는 경우

그래서 14501은 한 문제 풀이로 끝내기보다, 선택형 DP의 기본 예제로 기억해두기 좋다.

핵심은 dp 정의다

이 문제는 dp를 어떻게 정의하느냐가 가장 중요하다.

보통 이렇게 두면 가장 자연스럽다.

dp[i] = i번째 날부터 퇴사일까지 얻을 수 있는 최대 수익

이렇게 정의하면 i번째 날에서 할 수 있는 일은 간단해진다.

1. 오늘 상담을 하지 않는다
   → 다음 날로 넘어간다
   → dp[i+1]
2. 오늘 상담을 한다
   → 상담이 끝난 날 다음으로 넘어간다
   → p[i] + dp[i+t[i]]

단, 상담이 퇴사 전에 끝나야 하므로
i + t[i] <= n 조건을 확인해야 한다.

점화식은 다음처럼 정리된다.

if i + t[i] <= n:
    dp[i] = max(dp[i+1], p[i] + dp[i+t[i]])
else:
    dp[i] = dp[i+1]

이 식이 이 문제의 핵심이다.

왜 뒤에서부터 채우는가

이 문제는 바텀업으로 풀 때 뒤에서부터 앞으로 채운다. ( 그냥 웬만하면 바텀업으로..)

이유는 dp[i]를 구할 때 미래 값이 필요하기 때문이다.

• dp[i+1]
• dp[i+t[i]]

이 값들이 먼저 계산되어 있어야 현재 값을 정할 수 있다.
그래서 뒤에서 앞으로 오는 방식이 자연스럽다.

이 문제를 통해 DP는 항상 앞에서부터 누적하는 것이 아니라는 점도 함께 익힐 수 있다.

이 문제에서 배울 수 있는 점

14501은 기본적인 DP 사고를 연습하기 좋다.

먼저 상태를 어떻게 정의할지 생각해야 하고,
그다음 현재 선택지를 정리하고,
각 선택이 어디로 이어지는지 확인하면 된다.

이 문제를 풀면서 익혀둘 만한 포인트는 다음과 같다.

• dp[i]의 의미를 정확히 정하기
• 현재 선택지를 두 가지로 나누기
• 각 선택 뒤에 도착하는 다음 상태 찾기
• 현재 값은 다음 상태들의 결과로 결정된다는 점 이해하기

이 흐름은 다른 DP 문제를 풀 때도 그대로 도움이 된다.

코드

n = int(input())
t = []
p = []

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

dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    if i + t[i] <= n:
        dp[i] = max(dp[i + 1], p[i] + dp[i + t[i]])
    else:
        dp[i] = dp[i + 1]

print(dp[0])

 

 

14501은 DP 입문 문제로 정리해두기 좋다.
상태 정의가 분명하고, 점화식도 짧고, 사고 흐름도 깔끔하다.
비슷한 유형의 문제를 다시 만났을 때 기준점으로 삼기 좋은 문제였다.

앞으로 이런 문제를 보면 먼저 다음을 떠올리면 된다.

• dp[i]를 무엇으로 정의할지
• 현재 할 수 있는 선택이 무엇인지
• 선택마다 어디로 이동하는지
• 그 결과 중 최댓값을 고르면 되는지