[백준 C++] 1106번 호텔

1106번: 호텔

문제 요약

문제

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

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

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

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

사용 알고리즘

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

입출력

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

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

예제

입력
12 2
3 5
1 1
출력
8

풀이

전형적인 dp문제이다. 고객의 수를 기준으로 잡아 풀면 된다. i명의 고객상태일때 각 조건들을 비교하여 조건의 고객의 수만큼 i에서 빼서 거기서 조건의 비용을 더한것중 최소인걸 찾으면 된다.

어려웠던 점

일단 처음에는 c이상의 고객까지 가능한데 c까지만 적용해서 풀어서 틀렸다. c이상일때도 비용이 더 작아질 수 있다. 다음으로는 dp 배열의 값을 초기화 하지 않고 0일때 조건을 두고 풀었는데 값을 초기화 하는것이 확실하고 더 쉽게 풀 수 있었다. 초기화 하지 않으니 초반에 틀리는 경우가 있었다.

배운 점 / 느낀 점

dp를 풀 때에는 항상 초기화를 잘 하자

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, c, m, mm;
vector<int> dp;
vector<pair<int,int>> a;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    dp = vector<int>(2000, 1000000);
    dp[0] = 0;

    cin >> c >> n;

    a = vector<pair<int,int>>(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
        m = max(m, a[i].second);
    }

    for (int i = 1; i <= c+m; i++) {
        for (int j = 0; j < n; j++) {
            if(i-a[j].second >= 0){
                dp[i] = min(dp[i], dp[i-a[j].second]+a[j].first);
            }
        }
        if(i >= c){
            if(mm == 0){
                mm = dp[i];
            }
            else{
                mm = min(dp[i], mm);
            }
        }
    }
    cout << mm;
    

    return 0;
}