[BOJ] 1106 호텔

문제 요약

문제 링크: 백준 1106 - 호텔

 

문제 설명
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

---

접근 방법

• 배낭 문제에는 대표적으로 세 가지 유형이 있는데 이 문제는 그 중 무한 배낭 문제에 속한다.
  • 0-1 배낭 문제 (0-1 Knapsack): 각 아이템을 최대 1번만 선택할 수 있습니다.
  • 유한 배낭 문제 (Bounded Knapsack): 각 아이템을 정해진 횟수(k번)만큼만 선택할 수 있습니다.
  • 무한 배낭 문제 (Unbounded Knapsack): 각 아이템을 무제한으로 선택할 수 있습니다.
• 무한 배낭 문제로 접근하기 위해 DP 배열을 다음과 같이 정의한다.
  • dp[i]: 비용 i를 사용해 얻을 수 있는 최대 고객 수
• 이를 바탕으로 점화식을 세울 수 있다. k번째 도시의 홍보 비용이 cost, 얻는 고객 수가 customer일 때, 총비용 j에 대한 최대 고객 수는 다음과 같이 갱신된다.
  • dp[j] = max(dp[j], dp[j - cost] + customer)

---

코드

#include <bits/stdc++.h>
using namespace std;

int c, n, w[21], v[21], dp[100001];

void solve() {
    for (int i = 0; i <= 100000; i++) dp[i] = -1;
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = w[i]; j <= 100000; j++) { // unbounded knapsack
            if (dp[j - w[i]] != -1)
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    for (int i = 0; i <= 100000; i++) {
        if (dp[i] >= c) {
            cout << i;
            return;
        }
    }
}

void input() {
    cin >> c >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

마무리

• 무한 배낭(Unbounded Knapsack)를 활용하는 문제
• 전체 시간복잡도: O(N * M) ≈ 2,000,000