[PS] BOJ 29756 / DDR 체력 관리

Minjun Kim

23 Aug 2025 • 9 min read

문제 링크: https://www.acmicpc.net/problem/29756

Thumbnail: Photo by George Dagerotip (Unsplash)

조금만 생각해보면, 배낭 문제의 점화식을 응용해 풀이할 수 있습니다.

풀이

0-1 배낭 문제

풀이에 앞서, 0-1 배낭 문제의 아이디어를 다시 복습해봅시다.

$N$개의 물건에 대해, $i$번째 물건의 무게를 $W_i$, 가치를 $V_i$라고 하고 최대 $K$의 무게를 담을 수 있는 배낭이 있습니다. 이 배낭에 물건을 적절히 골라 담아서, 그 가치의 합이 최대가 되도록 하는 문제입니다.

0-1 배낭 문제는 물건을 쪼개서 담을 수 없습니다. 물건을 쪼개어 담는 문제는 Fractional Knapsack으로, 탐욕법(greedy)으로 풀 수 있습니다.

$i$번째 물건에 대해, 현재 배낭에 더 담을 수 있는 무게(남은 무게)를 $w$라고 하면 DP 배열을 채우는 과정은 다음과 같습니다.

K: int       # 배낭에 담을 수 있는 최대 무게
W: list[int] # 각 물건의 무게
V: list[int] # 각 물건의 가치

DP: list[list[int]] = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
for i in range(1, N + 1): 1번 물건부터 N번 물건까지
    for w in range(K):
        if W[i] > w: # 현재 배낭의 남은 무게로는 i번 물건을 담을 수 없다.
            DP[i][w] = DP[i - 1][w]
        else: # 배낭에 i번 물건을 담는 경우와 그렇지 않은 경우 중 가치가 최대가 되는 경우를 고려한다.
            DP[i][w] = max(DP[i - 1][w], V[i] + DP[i - 1][w - W[i]])

print(DP[N][K]) # 모든 무게에 대해 최댓값을 저장했으므로, DP 배열의 맨 끝값에 최대 가치가 저장된다.

0-1 배낭 문제 풀이

아이디어

이 문제의 구성이 배낭 문제와 유사합니다. 따라서, 0-1 배낭 문제의 점화식을 응용하는 방법을 생각했습니다.

곡은 $N$개의 구간으로 이루어져 있고 어떠한 구간 $i$ $(1 \le i \le N)$에 대해 코더빡은 해당 구간을 플레이할지, 포기할지 선택할 수 있다.

0-1 배낭 문제가 $N$개의 물건에 대해 그 물건을 배낭에 담을지 말지 결정하는 것과 같습니다.

해당 구간을 플레이할 때 얻을 수 있는 점수는 $s_i$점이며, 체력을 $h_i$만큼 소모한다. 구간을 포기할 때는, 점수를 얻지 못하고 체력도 소모하지 않는다.

물건을 배낭에 담으면, 그 가치만큼 배낭의 가치 총합이 증가하며, 동시에 남은 무게는 감소하는 것과 동일합니다.

곡이 시작할 때, 코더빡은 체력 $100$을 가지고 시작한다.

배낭에 담을 수 있는 무게 한도는 100입니다.

구간을 플레이했을 때 체력이 $0$ 미만으로 하락하는 경우 코더빡은 해당 구간을 포기해야만 한다.

배낭의 무게 한도 100을 모두 사용하면, 더 이상 물건을 담을 수 없습니다.

위 조건들은 모두 배낭 문제와 동일하게 생각해 볼 수 있으나, 다음 조건으로 인해 배낭 문제와 달라집니다.

매 구간에 진입하기 전에 체력을 $K$만큼 회복한다. 이 체력 회복은 구간을 플레이하거나 포기하는 것과는 무관하게 일어남에 유의하라. 회복 후 코더빡의 체력이 $100$을 초과하는 경우 체력이 $100$이 된다.

간단하게 생각해보면, 배낭 문제에서 한 물건을 담을지 말지 고민한 뒤 다음 물건으로 넘어갈 때 배낭의 남은 무게 한도가 $K$만큼 확장된다고 생각해볼 수 있습니다. 다만, 늘어난 배낭의 남은 무게 한도는 100을 넘지 않습니다. 이 과정을 DP를 계산하기 전에 먼저 반영해주면 됩니다.

점화식 세우기

다시 0-1 배낭 문제의 점화식을 살펴봅시다.

if W[i] > w: # 현재 배낭의 남은 무게로는 i번 물건을 담을 수 없다.
    DP[i][w] = DP[i - 1][w]
else: # 배낭에 i번 물건을 담는 경우와 그렇지 않은 경우 중 가치가 최대가 되는 경우를 고려한다.
    DP[i][w] = max(DP[i - 1][w], V[i] + DP[i - 1][w - W[i]])

0-1 배낭 문제의 점화식

먼저 이 문제에 맞게 표현을 바꿔봅시다.

$i$번 물건의 무게 W[i] → $i$번째 구간을 플레이할 때 잃는 체력의 양 H[i]
현재 배낭의 남은 무게 w → 현재 플레이어의 남은 체력 h
$i$번 물건의 가치 V[i] → $i$번 구간의 점수 S[i]

if H[i] > h: # 현재 플레이어의 남은 체력으로는 i번 구간을 플레이 할 수 없다.
    DP[i][h] = DP[i - 1][h]
else: # i번 구간을 플레이하는 것과 스킵하는 것 중 점수가 더 높은 경우를 택한다.
    DP[i][h] = max(DP[i - 1][h], S[i] + DP[i - 1][h - H[i]])

표현을 바꾼 점화식

이제, 체력 회복을 반영해주면 됩니다. 매번 새 구간에 진입할 때, 플레이할지 스킵할지 결정하기 전에 먼저 $K$만큼의 체력이 회복됩니다.

체력 회복에 따라 점화식의 구성을 변경해야 합니다.

1) 해당 구간을 스킵하는 경우

기존 배낭 문제에선 남은 무게가 변하지 않았지만, 이 문제에서는 체력 회복이 진행되었습니다. $i$번째 구간에서 회복된 체력으로 얻은 점수는 $i-1$번째 구간에서 회복하기 전 체력으로 얻은 점수와 같습니다.

2) 해당 구간을 플레이하는 경우

플레이어의 체력에 한 번 더 변화가 일어납니다. 이전에 회복한 체력에서 이 구간에서 요구하는 체력 만큼을 소모하게 됩니다.

after_heal = min(h + K, 100)

# 1. 스킵하는 경우
DP[i][after_heal] = DP[i - 1][h]
# 2. 플레이하는 경우
if after_heal >= H[i]:
    played_health = after_heal - H[i]
    DP[i][played_health] = S[i] + DP[i - 1][h]

체력 회복을 고려한 점화식

점화식을 정리해보니, 배낭 문제는 같은 DP 칸에 경우에 따라 다른 값을 채웠다면 이 문제는 애당초 값을 채우는 DP 칸도 경우에 따라 달라지는 것을 알 수 있습니다.

다시 말하면, 이전에 계산했던 DP 칸도 다시 계산될 수 있다는 뜻이니, 이를 고려해줘야 합니다.

for i in range(1, N + 1):
    for h in range(101):
        after_heal = min(h + K, 100)
        
        # 1. 스킵하는 경우
        DP[i][after_heal] = max(DP[i][after_heal], DP[i - 1][h])
        
        # 2. 플레이하는 경우
        if after_heal >= H[i]:
            played_health = after_heal - H[i]
            DP[i][played_health] = max(DP[i][played_health], S[i] + DP[i - 1][h])

최종 점화식

DP 배열 정의하고 결과 출력하기

이제, DP 배열을 정의해봅시다. 앞선 점화식을 토대로 다음과 같은 형태를 생각해볼 수 있습니다.

DP[구간 번호][남은 체력]

# 1...N의 구간에 대해 0...100의 체력을 계산한다.
DP = [[-1 for _ in range(101)] for _ in range(N + 1)]
DP[0][100] = 0 # 시작 지점

DP 배열 구성

DP 배열을 0으로 초기화해도 되지만, 보다 명시적으로 도달할 수 없는 경우를 구분하기 위해 -1로 초기화했습니다.

만약 0으로 초기화했다면, 계산 중인 경우가 실제로 가능한지 아닌지를 판단할 방법이 없습니다. 이 문제는 모든 구간을 플레이 하기 전, 체력이 100인 상태에서 시작할 때만 유일하게 가능한 경우이므로 이외의 경우가 계산된다면 DP 배열의 계산 값이 정확하지 않을 수 있습니다.

따라서, DP 배열의 모든 칸을 -1로 초기화한 뒤 유일하게 가능한 시작 지점인 DP[0][100]만 0으로 초기화해줍니다. 이후 DP 배열의 각 칸을 계산할 때 이전 칸의 값이 -1이었다면 불가능한 경우이므로 계산하지 않도록 합니다.

DP = [[-1 for _ in range(101)] for _ in range(N + 1)]
DP[0][100] = 0 # Only available start point.

for i in range(1, N + 1):
    for h in range(101):
        if DP[i - 1][h] == -1: # 실제로 가능한 경우가 아니면 계산하지 않는다.
            continue
        ... # 점화식

DP 배열의 정의 및 불가능한 경우 배제하고 계산하기

전체 코드

앞선 코드와는 다르게 $i$번 구간의 정보를 S[i-1], H[i-1]로 참조하고 있습니다. 이는 DP 배열에서는 각 구간 번호를 1부터 $N$까지로 사용했지만 입력 배열에서는 0부터 $N-1$까지로 저장했기 때문입니다.

input = open(0).readline
N, K = map(int, input().split())
S = list(map(int, input().split()))
H = list(map(int, input().split()))
DP = [[-1 for _ in range(101)] for _ in range(N + 1)]
DP[0][100] = 0 # Only available start point.

for i in range(1, N + 1):
    for h in range(101):
        if DP[i - 1][h] == -1: # This isn't valid case.
            continue

        # In every section, player's hp is healed first.
        after_heal = min(h + K, 100)
        
        # Case 1) Skip this section.
        DP[i][after_heal] = max(DP[i][after_heal], DP[i - 1][h]) # healed.

        # Case 2) Play this section.
        if after_heal >= H[i - 1]:
            played_health = after_heal - H[i - 1]
            DP[i][played_health] = max(DP[i][played_health], S[i - 1] + DP[i - 1][h])

print(max(DP[N]))

solution.py