BOJ 1106 - 호텔

문제 요약

고객을 최소 C명 이상 늘려야 한다. N개의 도시가 있고, 각 도시에서 홍보하면 일정 비용으로 일정 수의 고객이 늘어난다. 같은 도시에서 여러 번 홍보할 수 있다. 최소 비용을 구하라.

(GTA의 카지노 홍보 미션이 떠오른다. 버자드 타고 전단지 뿌렸던것 같은데..)

처음 접근 — 2D DP (2차원)

처음엔 자연스럽게 2D DP로 접근했다.

dp[i][c] = i번 도시까지 고려했을 때, 고객 c명을 늘리는 최소 비용

익숙한 배낭 문제 구조처럼 보였기 때문이다. 보통 배낭 문제는 dp[i][w] — i번째 물건까지 고려했을 때 무게 w 이하에서의 최대 가치 — 형태로 풀었던 전적이 있기 때문이다.

내 최초 코드

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int C, N;
    cin >> C >> N;
    
    vector<int> money(N+1);
    vector<int> customer(N+1);
    for(int i = 0; i < N; i++){
        int m, c;
        cin >> money[i] >> customer[i];
    }
    vector<vector<int>> dp(N, vector<int>(C+1, 0));
    for(int i = 0; i < N; i++){
        for(int c = 1; c <= C; c++){
            if(i == 0){
                dp[i][c] = ((c + customer[i]-1) / customer[i]) * money[i];
            }
            else{
                if(c - customer[i] >= 1){
                    dp[i][c] = min({dp[i-1][c], (((c + customer[i]-1) / customer[i]) * money[i]),dp[i][c-customer[i]] + money[i]});
                }
                else{
                    dp[i][c] = min(dp[i-1][c], (((c + customer[i]-1) / customer[i]) * money[i]));
                }
            }
        }
    }
    
    cout << dp[N-1][C];
    
    return 0;
}

AC는 났다. (뽀록)
하지만 코드를 다시 보면 조건 분기가 지저분하고, 올림 나눗셈 (c + customer[i]-1) / customer[i]으로 엣지 케이스를 우회한 흔적이 역력하다. (올림하는 식임)
뭔가 억지로 맞춘 느낌.

왜 2D로 접근했을까?

"도시를 여러 번 쓸 수 있다"는 조건을 제대로 소화하지 못했기 때문이다.

일반적인 0/1 배낭 문제는 각 물건을 한 번씩만 쓸 수 있어서, "어디까지 고려했는가"를 추적하는 i 차원이 필요하다. 그 패턴에 익숙하다 보니 이 문제도 반사적으로 2D로 짰다.

하지만 이 문제는 unbounded knapsack — 같은 도시를 몇 번이든 쓸 수 있다. 이 경우 "어떤 도시까지 고려했냐"는 차원 자체가 필요 없다. 고객 수만 추적하면 충분하다.

핵심 질문: 이 아이템을 여러 번 쓸 수 있는가?

Yes → 1D DP (unbounded knapsack)

No → 2D DP (0/1 knapsack)

배낭 문제 (Knapsack) 소개

배낭 문제는 DP의 대표적인 유형이다. 기본 구조는 이렇다.

용량 W인 배낭에 N개의 물건을 담을 때, 가치를 최대화하라.

0/1 Knapsack

각 물건을 최대 한 번만 쓸 수 있다.

dp[i][w] = i번째 물건까지 고려했을 때, 무게 w 이하에서의 최대 가치

물건을 중복 사용하지 못하므로 i 차원으로 "어디까지 봤는가"를 추적한다.

Unbounded Knapsack

각 물건을 횟수 제한 없이 쓸 수 있다.

dp[w] = 무게 w를 채우는 최적값

i 차원이 필요 없다. 모든 아이템을 매번 다시 고려하면 된다.

이번 호텔 문제는 unbounded knapsack의 최소 비용 버전이다.

개선된 접근 — 1D DP

dp[i] = 고객을 i명 늘리는 최소 비용
dp[0] = 0  (아무것도 안 해도 0명 늘리는 비용은 0)

점화식:

dp[i] = min(dp[i], dp[max(0, i - customer[j])] + money[j])  for all j

max(0, i - customer[j])는 고객 증가량이 i를 초과할 때도 자연스럽게 처리해준다. dp[0] = 0이기 때문에 별도 분기 없이 처리된다.
(싫으면 그냥 0 기준으로 분기처리해도 됨.)

최종 코드

#include<bits/stdc++.h>
using namespace std;
int INF = 1e9;
int main()
{
    int C, N;
    cin >> C >> N;
    vector<int> money(N);
    vector<int> customer(N);
    for(int i = 0; i < N; i++){
        cin >> money[i] >> customer[i];
    }
    vector<int> dp(C+1, INF);
    dp[0] = 0;
    for(int i = 1; i <= C; i++){
        for(int j = 0; j < N; j++){
            dp[i] = min(dp[i], dp[max(0, i-customer[j])] + money[j]);
        }
    }
    cout << dp[C];
    
    return 0;
}

비교 정리

| 항목 | 최초 코드 | 최종 코드 | |------|-----------|-----------| | DP 차원 | 2D (N × C) | 1D (C) | | 공간복잡도 | O(NC) | O(C) | | 시간복잡도 | O(NC) | O(NC) | | 코드 복잡도 | 조건 분기 多 | 단순 | | 설계 명확성 | 낮음 | 높음 |

시간복잡도는 같지만, 공간과 코드 가독성에서 1D가 압도적으로 낫다.

회고

AC가 났다고 끝이 아니었다. 코드를 뜯어보니 내가 문제의 핵심 조건 — 중복 사용 가능 — 을 제대로 소화하지 않고, 익숙한 2D 패턴에 억지로 끼워 맞췄다는 게 보였다.

배낭 문제에서 아이템을 여러 번 쓸 수 있는지 없는지를 먼저 확인하는 습관을 들이자. 그게 DP 차원 설계의 출발점이다.