[BOJ] 1106 - 호텔

https://www.acmicpc.net/problem/1106

BOJ - 호텔

문제 유형: 다이나믹 프로그래밍, 배낭 문제

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

풀이

dp[customer] = 해당 customer만큼 늘리기 위한 최소 비용으로 두고, 범위를 c+100이상으로 둔 다음, 배낭 문제로 푼다.

dp[c] ~ dp[c+100]의 범위 중 최소값을 반환하면, c이상의 손님을 불러오는 경우의 수들 중 최소값을 구할 수 있다.

c+100인 이유는 한 번의 최대 홍보로 얻는 양이 100이기 때문이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int c, n;
    cin >> c >> n;
    vector<pair<int, int>> ads(n);  // cost, customer;
    for (int i = 0; i < n; i++) {
        cin >> ads[i].first >> ads[i].second;
    }
    vector<int> dp(c + 101, 1e9);
    dp[0] = 0;

    for (int i = 1; i <= c + 100; i++) {
        for (const auto &[cost, customer] : ads) {
            if (i - customer >= 0) {
                dp[i] = min(dp[i], dp[i - customer] + cost);
            }
        }
    }

    cout << *min_element(dp.begin() + c, dp.end()) << "\n";

    return 0;
}