[AlgorithmSolving][DP] JUNGOL_4480: 마법 수리공

1. 문제 내용

• 문제:

  판타지세계에 사는 수리공 창하는 마법을 이용하여 손님들의 물품들을 수리해 주고 돈을 받는다.

  창하는 이 세계관에서 물건 수리하는 일을 제일 잘 하기 때문에(다른 수리공들은 마법을 쓰지 못한다) 인기가 매우 많다.

  그러므로 손님들은 항상 줄을 서서 수리를 받는다. 현재 N명이 줄을 서 있다.

  물품 종류에 상관없이 수리하는 일은 항상 1분이 걸린다. 따라서 모든 일이 진행되는데는 총 N분이 걸린다. 좋은 물품일수록 수리하는데 사용하는 “마법력”이 많이 든다. 또한 그만큼 수리비도 많이 받을 수 있다.

  구체적으로, i번째 손님의 물품의 가치는 C_i이다. 창하가 이 물품을 수리하는데는 C_i만큼의 마법력이 들며, 그 보상으로 받는 돈도 C_i원이다.

  모든 손님들의 요구를 다 들어주면, 창하의 마법력이 너무 빨리 바닥나기 때문에, 창하는 i번째 손님을 맞이함에 있어서 다음 두 가지 중 한 가지 행동을 할 수 있다.

  C_i의 마법력을 들여서 물품을 수리해주고, C_i원을 받는다.

  그 손님을 그냥 집으로 보내버리고, “미안” 한마디정도 던져준다(그 손님은 화가 많이 나겠지만, 괜찮다. 어차피 뒤에 돈 내고 수리하기 위한 손님들은 많다.)

  창하는 이 순간 곧바로 다음 손님을 받는 것이 아니라 1분간 명상하면서 마법력을 회복한다. 이 1분 동안 창하는 M의 마법력을 회복할 수 있다. (참고로 마법력은 최대치가 없으므로, 명상만 많이 한다면 얼마든지 늘어난다.)

  명상 후, 창하는 다음 손님을 맞이한다.

  처음에 창하의 총 마법력은 K이다.

  줄을 서 있는 N명의 손님이 수리해야 할 물건이 순서대로 주어졌을 때, 창하가 물품을 수리하여 받을 수 있는 금액의 최대치를 구하는 프로그램을 작성하라.

• 입력:

  첫 줄에 N, M, K가 각각 공백을 사이에 두고 주어진다. N은 줄을 서 있는 손님의 명수이다. 

  M은 창하가 명상하면서 회복할 수 있는 마법력이며, K는 초기 창하의 마법력이다.

  둘째 줄에 i번째 손님의 수리할 물품의 가치를 나타내는 C_i가 공백을 사이에 두고 주어진다.

  모든 부분문제에서 1≤N≤500, 0≤M≤100, 1≤K≤10,000, 1≤C_i≤10,000을 만족한다.

• 출력:

  창하가 받을 수 있는 총 수리비의 최댓값을 첫 줄에 출력한다.

2. 문제 유형 파악

해당 문제는 “0/1 배낭 문제”의 응용 문제이며, DP 배열의 초기값 설정과 DP 배열의 최적화를 진행해야 시간초과를 받지 않고 문제를 풀 수 있습니다.

3. 문제를 풀기 위한 핵심 아이디어

1. DP 배열의 상태(State) 정의

   문제에서 주어지는 ‘마법력’이 바로 배낭의 용량 역할을 합니다. 따라서 DP 배열의 인덱스를 마법력으로, 배열의 값을 수리비(돈)로 정의합니다.

   • DP[j] : 현재 남은 마법력이 j일 때 얻을 수 있는 최대 수리비

2. 두 가지 갈래의 상태 전이 (점화식)

   i번째 손님을 맞이했을 때, 우리가 할 수 있는 행동은 2가지입니다. 이전 고객까지 계산된 상태(현재 마법력 j)에서 다음 두 갈래로 뻗어나갑니다.

   • 선택A (수리한다):

     현재 마법력이 $C_i$ 이상일 때만 가능합니다. 마법력을 $C_i$ 소모하는 대신, $C_i$ 만큼의 돈을 법니다.

     • 상태 변화: ‘DP[j - C_i] = max(기존 값, DP[j] + C_i)’

   • 선택 B(명상한다/패스):

     마법력을 소모하지 않고 오히려 $M$만큼 회복합니다. 돈은 벌지 못합니다.

     • 상태 변화: ‘DP[j+M] = max(기존 값, DP[j])’

3. 마법력의 최댓값 계산 및 초기화 주의점

   이 문제에서 가장 실수하기 쉬운 부분은 배열의 크기와 초기화 입니다.

   1. 배열의 최대 크기 설정:

      • 마법력은 최대치는 따로 언급되지 않지만 문제를 보면 최대 마법력 상한선을 구할 수 있습니다 그 값은 K + (N * M) 입니다.
      • 입력 제한에 따라 $10000 + (500 \times 100) = 60000$ 이므로, DP 배열의 최대 크기는 60001이 됩니다.

   2. 초기화는 0이 아닌 -1로:

      도달할 수 없는 마법력 상태를 구분하기 위해, DP 배열은 0이 아닌 -1로 초기화 해야 합니다. 또한 초기 DP 배열에서 창하가 초기에 가지고 있는 마법력인 K 부분에 값을 0으로 초기화 해주어야 합니다. 창하의 마법력이 K만큼 있는 상태에서 손님을 하나도 받지 않았기 때문에 비용은 0이기 때문입니다.

   3. 1차원 배열 갱신 시 주의점:

      하나의 1차원 배열로 갱신을 진행하면, 이번 턴(현재 고객)에서 계산된 결과가 같은 턴의 다른 계산에 영향을 미치는 문제가 발생합니다. 따라서 ‘next_dp’라는 임시 배열을 하나 더 만들어 이번 고객의 결과를 모두 임시 배열에 기록한 뒤, 턴이 끝날 때 원본 ‘DP’ 배열에 덮어씌우는 방식을 사용해야 합니다.

4. 코드

해당 문제의 풀이 코드는 다음과 같습니다.

import sys

def solve():
    # 1. 입력 속도 최적화
    input = sys.stdin.readline
    n, m, k = map(int, input().split())
    costs = list(map(int, input().split()))

    # 현재 도달 가능한 '최대 마법력' 한계선
    current_max_magic = k
    
    # 2. 딕셔너리 대신 '필요한 만큼만' 1차원 리스트 할당
    dp = [-1] * (current_max_magic + 1)
    dp[k] = 0

    for cost in costs:
        # 이번 손님을 응대(명상)하고 난 뒤의 최대 마법력 한계선
        next_max_magic = current_max_magic + m
        
        # 다음 상태를 기록할 새로운 리스트 (미리 -1로 채워서 할당)
        next_dp = [-1] * (next_max_magic + 1)

        # 3. 6만 번을 고정으로 돌지 않고, 현재 한계선까지만 탐색 (동적 범위)
        for magic in range(current_max_magic + 1):
            money = dp[magic]
            
            # 도달할 수 없는 상태면 패스
            if money == -1:
                continue
                
            # [선택 1] 명상하기
            meditate_magic = magic + m
            # 4. max() 함수 호출을 없애고 직관적인 if문 대소 비교 사용 (속도 극대화)
            if money > next_dp[meditate_magic]:
                next_dp[meditate_magic] = money
            
            # [선택 2] 수리하기
            if magic >= cost:
                repair_magic = magic - cost
                repair_money = money + cost
                if repair_money > next_dp[repair_magic]:
                    next_dp[repair_magic] = repair_money

        # 배열 교체 및 한계선 갱신
        dp = next_dp
        current_max_magic = next_max_magic

    # 저장된 돈 중 최댓값 출력
    print(max(dp))

solve()

5. 복기 및 최적화

이번 ‘수리공 창하’ 문제를 풀면서 파이썬 환경에서 메모리와 연산 속도를 극한으로 끌어올리기 위해 적용한 최적화 기법들을 복기해 봅니다.

5.1 메모리 최적화: 1차원 배열 토글링 (Toggling)

이 문제를 2차원 배열 DP[손님 순서][마법력]으로 선언할 경우, 손님이 500명이고 최대 마법력이 약 60,000이라면 500 x 60,000 크기의 거대한 리스트가 생성되어 메모리 낭비가 심해집니다.

• 최적화 적용: $i$번째 손님의 상태는 오직 직전인 $i-1$번째 손님의 상태만 참조한다는 점을 이용했습니다.
• 결과: 전체 2차원 배열을 만들지 않고, dp와 next_dp라는 두 개의 1차원 배열만 번갈아 가며 덮어쓰는(토글링) 방식을 사용하여 공간 복잡도를 획기적으로 줄였습니다.

5.2 시간 최적화 1: 동적 탐색 범위 제한 (Dynamic Range)

단순하게 생각하면 1차원 배열을 갱신할 때마다 0부터 이론상 가능한 최대 마법력(초기 마법력 + N*M)까지 반복문을 돌아야 합니다.

• 최적화 적용: 초반에 손님이 몇 명 지나지 않았을 때는 도달할 수 있는 최대 마법력 한계치가 낮습니다. 따라서 고정된 최대치가 아니라, 매 턴마다 ‘현재 도달 가능한 최대 마법력(current_max_magic)’까지만 탐색하도록 반복문(for)의 범위를 동적으로 제한했습니다.
• 결과: 무의미하게 남은 배열을 순회하는 횟수를 극적으로 잘라내어 연산 시간을 대폭 단축했습니다.

5.3 시간 최적화 2: 파이썬 특화 미세 최적화 (Micro-optimization)

DP 문제를 풀 때 값을 갱신하기 위해 습관적으로 max() 함수를 자주 사용합니다. 하지만 파이썬에서 내장 함수 호출은 내부적으로 오버헤드(Overhead)를 발생시킵니다.

• 최적화 적용:

  # 기존 방식 (함수 호출 오버헤드 발생)
  next_dp[meditate_magic] = max(next_dp[meditate_magic], money)
      
  # 최적화 방식 (단순 대소 비교)
  if money > next_dp[meditate_magic]:
      next_dp[meditate_magic] = money
  

• 결과: 수백만 번 돌아가는 DP의 이중 루프 내부에서 max() 대신 직관적인 if 조건문을 사용하여 상태를 갱신했습니다. 알고리즘의 시간 복잡도 자체가 변하는 것은 아니지만, 파이썬 환경에서는 실제 실행 시간을 유의미하게 단축할 수 있는 매우 유용한 실전 팁입니다.