핵심 요약
- Unbounded Knapsack(무제한 배낭) 유형은 물건을 중복해서 사용할 수 있다는 점이 특징이며, 1차원 배열로 최적화가 가능합니다.
- 가장 중요한 것은 반복문의 중첩 순서(Loop Order)입니다. ‘비용(Cost)’과 ‘물건(Item)’ 중 무엇이 바깥쪽 루프에 위치하느냐에 따라 순열(Permutation)과 조합(Combination)으로 성격이 완전히 바뀝니다.
- 백준 1106번(호텔)과 같은 최적화(Min/Max) 문제에서는 순서가 결과값에 영향을 주지 않지만, 동전 교환 같은 경우의 수(Counting) 문제에서는 루프 순서가 정답을 가르는 핵심 키(Key)가 됩니다.
목차
- 1. 서론: 같은 식, 다른 결과의 미스터리
- 2. 순열 vs 조합: 루프의 위치가 결정한다
- 3. 백준 1106번으로 보는 두 가지 시선
- 4. 왜 호텔 문제는 둘 다 정답일까?
- 5. 실전 공식: 무엇을 밖으로 뺄 것인가?
1. 서론: 같은 식, 다른 결과의 미스터리
DP 문제를 풀다 보면 점화식은 똑같은데, 반복문(for)의 안쪽과 바깥쪽 순서를 바꿨더니 답이 달라지거나 시간 초과가 해결되는 경험을 하게 됩니다. 특히 Unbounded Knapsack(물건을 무한히 쓸 수 있는 배낭 문제)에서 이 현상이 두드러집니다.
많은 입문자가 “어차피 모든 경우를 다 해보는 건데 순서가 무슨 상관이야?”라고 생각합니다. 하지만 DP 테이블을 채워 나가는 순서는 ‘중복을 허용할 것인가(순서 인정)’와 ‘중복을 배제할 것인가(순서 무시)’를 결정짓는 아주 중요한 논리적 장치입니다. 이번 리포트에서는 백준 1106번(호텔) 문제를 통해 이 메커니즘을 해부해 봅니다.
2. 순열 vs 조합: 루프의 위치가 결정한다
우리가 3을 만든다고 가정해 봅시다. (1, 2 사용 가능)
- 순열(Permutation): {1, 2}와 {2, 1}을 다르게 봅니다. (총 2가지)
- 조합(Combination): {1, 2}와 {2, 1}을 같게 봅니다. (총 1가지)
Case A: 비용(Cost)이 바깥쪽일 때 (순열)
바깥쪽 반복문이 ‘비용(Cost)’을 순회하고, 그 안쪽에서 ‘물건(Item)’을 순회하는 구조입니다. 비용 1원부터 100원까지 차례대로 채워 나갑니다. 예를 들어 비용 5원을 만들 때, [2원+3원]도 시도하고 순서가 바뀐 [3원+2원]도 시도하게 됩니다. 즉, 순서가 섞이는 모든 경우를 탐색합니다.
Case B: 물건(Item)이 바깥쪽일 때 (조합)
바깥쪽 반복문이 ‘물건(Item)’을 하나씩 고정하고, 안쪽에서 ‘비용(Cost)’을 순회하는 구조입니다. 물건 A만으로 1~100원을 쭉 훑고, 그 상태에서 물건 B로 1~100원을 다시 훑습니다. 이렇게 하면 무조건 [물건 A 사용] → [물건 B 사용] 순서로만 계산됩니다. [물건 B]를 먼저 쓰고 나중에 [물건 A]를 쓰는 경우는 원천 봉쇄되므로 중복이 사라지고 조합만 남습니다.
3. 백준 1106번으로 보는 두 가지 시선
백준 1106번(호텔) 문제를 해결하는 두 가지 스타일의 전체 코드를 비교해 봅니다. 두 코드 모두 정답이지만, 탐색 방식에 차이가 있습니다.
Style 1: 순열 접근 (비용이 바깥쪽)
처음에 작성하셨던 직관적인 방식입니다. “비용 i를 만들기 위해 마지막에 무슨 도시를 선택했지?”를 고민합니다.
import java.util.*;
class Main {
static int n, m;
static int[] costs;
static int[] values;
public static int solution() {
// 비용 최대치: 고객 1000명 * 비용 100원 = 100,000원까지 가능
int[] dp = new int[100001];
// [순열 방식] 바깥쪽 루프: 비용(Cost)
// 1원부터 100,000원까지 차례대로 채워나감
for (int i = 1; i <= 100000; i++) {
// 안쪽 루프: 도시(Item)
// 현재 비용 i를 만들기 위해 모든 도시를 다 시도해봄 (순서 섞임 발생)
for (int j = 0; j < m; j++) {
int cost = costs[j];
int value = values[j];
if (i - cost >= 0) {
dp[i] = Math.max(dp[i], dp[i - cost] + value);
}
}
}
// 목표 고객 n명 이상을 얻는 최소 비용 찾기
int ans = 0;
for (int i = 0; i <= 100000; i++) {
if (dp[i] >= n) {
ans = i;
break;
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
costs = new int[m];
values = new int[m];
for (int i = 0; i < m; i++) {
costs[i] = sc.nextInt();
values[i] = sc.nextInt();
}
System.out.println(solution());
}
}
Style 2: 조합 접근 (물건이 바깥쪽) - 권장
배낭 문제의 정석(Standard) 패턴입니다. "이 도시만으로 채워보고, 다음 도시를 추가해보자"는 식입니다. 이 방식은 순서가 강제되므로 중복 카운팅이 발생하지 않습니다.
import java.util.*;
class Main {
static int n, m;
static int[] costs;
static int[] values;
public static int solution() {
int[] dp = new int[100001];
// [조합 방식] 바깥쪽 루프: 도시(Item)
// 도시 하나를 고정하고 비용 전체를 훑음
for (int j = 0; j < m; j++) {
int cost = costs[j];
int value = values[j];
// 안쪽 루프: 비용(Cost)
// 정방향 순회 -> 물건 중복 사용 허용 (Unbounded)
// 시작점을 cost로 잡으면 if문도 필요 없음
for (int i = cost; i <= 100000; i++) {
dp[i] = Math.max(dp[i], dp[i - cost] + value);
}
}
int ans = 0;
for (int i = 0; i <= 100000; i++) {
if (dp[i] >= n) {
ans = i;
break;
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
costs = new int[m];
values = new int[m];
for (int i = 0; i < m; i++) {
costs[i] = sc.nextInt();
values[i] = sc.nextInt();
}
System.out.println(solution());
}
}
4. 왜 호텔 문제는 둘 다 정답일까?
여기서 의문이 생깁니다. "순열과 조합은 결과가 다르다며? 왜 1106번은 둘 다 정답이야?"
그 이유는 이 문제가 '경우의 수(Counting)'가 아니라 '최적값(Optimization)'을 묻기 때문입니다.
- 경우의 수 문제 (예: 동전 1): {1, 2}와 {2, 1}을 다르게 세면 답이 2배가 되므로 오답입니다. 반드시 조합(Style 2)을 써야 합니다.
- 최적값 문제 (예: 호텔): {도시A, 도시B}를 써서 고객 10명을 모으나, {도시B, 도시A}를 써서 고객 10명을 모으나, "최대 10명"이라는 결과값(Value)은 동일합니다.
Math.max(10, 10)은 10이니까요.
따라서 호텔 문제는 논리적으로는 차이가 있지만, 결과적으로는 둘 다 정답 처리가 됩니다. 하지만 CPU 캐시 효율성(Cache Locality) 면에서는 하나의 물건으로 배열을 쭉 훑는 Style 2(조합)가 아주 미세하게 유리합니다.
5. 실전 공식: 무엇을 밖으로 뺄 것인가?
실전 코딩 테스트에서 헷갈리지 않기 위한 절대 공식을 정리해 드립니다.
📌 DP 루프 순서 결정 공식
- 동전의 개수 / 경우의 수 (Counting):
- 순서가 중요하면(1+2 != 2+1)? → 비용(Cost)이 바깥! (순열)
- 순서가 무관하면(1+2 == 2+1)? → 물건(Item)이 바깥! (조합) *가장 흔함
- 최대 가치 / 최소 비용 (Optimization):
- 아무거나 써도 됨.
- 하지만 헷갈림 방지를 위해 '물건(Item)이 바깥'인 조합 스타일로 통일하는 것을 강력 추천합니다.
이제 백준 1106번을 넘어 다른 배낭 문제를 만나더라도, "이건 순서가 중요한가?"라는 질문 하나로 반복문의 위치를 바로 결정하실 수 있을 겁니다.
💡 더 알아보기: 반복문의 순서에 따라 정답/오답이 결정되는 문제가 궁금하다면 무한 배낭 문제 포스트를 참고하세요.