[DP] Unbounded Knapsack(무한 배낭 문제)

목차

• 1. 배낭은 배낭인데, 마르지 않는 배낭?
• 2. 순열 vs 조합: 반복문 순서의 비밀
• 3. 점화식 해부: dp[v] += dp[v – coin]
• 4. 결론: 손보다 머리가 먼저 움직여야 한다

오늘은 알고리즘계의 스테디셀러, 백준 2293번 ‘동전 1’ 문제를 통해 Unbounded Knapsack(무한 배낭 문제)을 파헤쳐 보려 합니다. 많은 입문자가 “어? 분명 로직은 맞는데 왜 답이 틀리지?”라며 좌절하는 구간이기도 하죠. 그 원인은 바로 ‘반복문의 순서’에 숨겨져 있습니다. 실제 오답 코드와 정답 코드를 비교하며 그 비밀을 풀어드립니다.

1. 배낭은 배낭인데, 마르지 않는 배낭?

일반적인 배낭 문제(0/1 Knapsack)는 물건을 “넣느냐, 마느냐” 딱 한 번만 결정합니다. 하지만 오늘 다룰 Unbounded Knapsack은 다릅니다.

• 상황: 여러분 앞에는 1원, 2원, 5원짜리 동전이 무한대로 쌓여 있습니다.
• 목표: 이 동전들을 합쳐서 정확히 K원을 만드는 경우의 수를 구해야 합니다.

즉, 같은 동전을 여러 번 써도 된다는 점이 핵심입니다. 이 ‘무한한 자유’ 때문에 우리는 DP 테이블을 채울 때 앞에서 뒤로(작은 금액 → 큰 금액) 나아가며 값을 누적시킬 수 있습니다.

2. 순열 vs 조합: 반복문 순서의 비밀

이 문제의 오답률을 높이는 주범은 바로 “1+2와 2+1을 같게 볼 것이냐, 다르게 볼 것이냐”입니다. 문제에서는 “순서만 다른 것은 같은 경우”라고 했으니 조합(Combination)을 구해야 합니다.

❌ 실패 케이스: 목표 금액이 바깥쪽인 경우 (순열)

먼저 많은 분들이 실수하는 패턴입니다. “일단 금액 V를 만들기 위해 동전들을 다 대입해 보자”라고 생각하면 아래와 같은 코드가 나옵니다.

import java.util.*;

class Main {

  static int n, k;
  static int[] coins;
  static int[] dp;

  static void run() {
    for (int v = 1; v <= k; v++) {
      for (int coin : coins) {
        if (v - coin >= 0 && dp[v - coin] > 0) {
          dp[v] += dp[v - coin];
        }
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    k = sc.nextInt();
    coins = new int[n];
    for (int i = 0; i < n; i++) coins[i] = sc.nextInt();

    dp = new int[k + 1];
    dp[0] = 1;
    run();

    System.out.println(dp[k]);
  }

}

왜 틀렸을까요?
이 코드는 "방금 1원을 썼어도, 다음 스텝에서 다시 2원을 쓸 수 있고, 그 다음 스텝에서 또 1원을 쓸 수 있다"는 논리입니다. 즉, 1+2를 카운트한 뒤에, 나중에 2+1도 별개의 경우로 카운트합니다. 순서가 중요해지는 순열(Permutation)이 되어버려 답이 훨씬 크게 나옵니다.

⭕ 성공 케이스: 동전이 바깥쪽인 경우 (조합)

이 문제를 해결하려면 반복문의 순서를 딱 한 번만 뒤집으면 됩니다. 동전을 주인공으로 만드세요.

// [수정된 코드] 동전(coin)을 바깥쪽 루프로 뺍니다.
static void run() {
    // 1. 동전을 하나씩 꺼내서 '주인공'으로 설정합니다. (1원 처리 -> 2원 처리 -> ...)
    for (int coin : coins) {
        
        // 2. 해당 동전으로 만들 수 있는 금액들만 갱신합니다.
        for (int v = coin; v <= k; v++) {
            dp[v] += dp[v - coin];
        }
    }
}

왜 정답일까요?
이 방식은 "1원 처리가 끝나면, 다시는 1원을 돌아보지 않겠다"는 선언과 같습니다. 1원으로 만들 수 있는 모든 경우를 채운 뒤에야 2원을 섞기 시작하므로, 자연스럽게 1+2는 가능하지만 2+1(2원 뒤에 1원)은 불가능해집니다. 동전의 사용 순서가 강제되므로 중복이 사라지는 것이죠.

3. 점화식 해부: dp[v] = dp[v] + dp[v - coin]

DP의 심장, 점화식을 해석해 봅시다. 이 식은 "현재 금액 v를 만드는 방법의 수"를 정의합니다.

dp[v] += dp[v - coin]

• dp[v] (기존 값): 이번 동전(coin)을 전혀 쓰지 않고, 이전에 사용했던 동전들만으로 v원을 만드는 방법의 수입니다.
• dp[v - coin]: 이번 동전(coin)을 최소한 하나 이상 사용하는 경우입니다. v원에서 동전 값만큼 뺀 금액(v - coin)을 만드는 방법에, 이번 동전을 '탁' 얹는 것과 같습니다.

4. 결론: 손보다 머리가 먼저 움직여야 한다

많은 입문자가 "일단 `for`문부터 적고 보자"는 유혹에 빠집니다. 하지만 위의 두 코드가 보여주듯, 반복문의 순서 하나가 알고리즘의 성격(순열 vs 조합)을 완전히 바꿔버립니다.

DP 문제를 만났을 때 가장 먼저 해야 할 일은 키보드를 두드리는 게 아닙니다.

1. 정의: dp[i]가 무엇을 의미하는지 정의하고,
2. 관계: 현재 문제와 작은 문제 사이의 관계식, 즉 점화식을 노트에 먼저 끄적여야 합니다.

점화식이 명확하다면, 코드는 그저 그 식을 옮겨 적는 수단일 뿐이니까요.