[c++] 백준 1106 호텔 - 동적계획법

[문제]

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

1106번: 호텔

 

[풀이]

동적계획법(dp) 문제이다.(dp에 대한 감을 아예 잃어서 뻘짓만 했다...)

dp[i] = i만큼의 비용을 들여 확보할 수 있는 최대 고객 수 라고 해보자.

C는 최대 1000이고, 도시를 홍보하는 최대 비용은 100이다. 100에 고객 1명을 확보할 수 있다면 1000명의 고객을 확보하는데 필요한 비용, dp의 최대 크기는 1000*100+1이 된다. 따라서 dp[100001] 배열을 선언한다.

먼저 i의 비용으로 확보할 수 있는 최대 고객 수는 n개의 도시에 대해서 다음과 같이 생각해 볼 수 있다.

12 2
3 5
1 1

dp[1] = 1

dp[2] = 2

dp[3] = 5  

dp[4] = 6

dp[5] = 7 

dp[6] = 10 -> 3과 1로 나누어 떨어지므로 5*2, 1*6 중 최댓값인 10.

dp[7] = 11 -> 이전 최댓값에 한번 더 홍보하는 값.

n개의 도시에 투자 가능한 비용으로 나누어 떨어지는 경우에는 이에 대한 정수배의 투자가 가능하므로 dp[i] = max(dp[i], (i/3)*5 또는 (i/1)*1)로 갱신해줄 수 있다.

또한 모든 경우에 이전 최댓값에 한 번 더 홍보를 해주는 값과 비교해서 갱신해 줄 수 있다. 예를 들어, dp[5]의 경우 5>3 이므로 dp[5-3]인 2(이전 최댓값) + 5(3으로 한번 더 홍보해주는 값)인 7로 생각할 수 있다.

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;

int dp[100001];

int main() {
    //홍보를 할 수 있는 도시, 도시를 홍보하는데 드는 비용, 몇 명의 고객이 늘어나는지.
    //정수배만큼 투자 가능.
    //호텔의 고객을 적어도 c명 늘리기 위해 투자해야 하는 최소 비용을 구하시오.
    int c, n;
    cin >> c >> n;
    vector<pair<int, int>> v(n);

    for(int i=0; i<n; i++) {
        int cost, customer;
        cin >> cost >> customer;
        v[i] = {cost, customer};
    }

    for(int i=1; i<=100000; i++) {
        for (int j = 0; j < n; j++) {
            if(i%v[j].first==0){
                dp[i] = max(dp[i], (i/v[j].first)*v[j].second);
            }
            if(i-v[j].first >= 0){
                dp[i] = max(dp[i], dp[i-v[j].first]+v[j].second);
            }
        }
        if(c<=dp[i]){
            cout << i; //최소 비용
            return 0;
        }
    }
}