[Gold 5] 1106 호텔

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

1106번: 호텔

 

이 문제는 배낭을 활용해서 해결할 수 있다.

 

배낭은 호텔에서 수용가능한 인원의 크기 만큼 담아야 한다.

호텔에서 수용가능한 인원의 크기는 최대 인원 수 * 최대 홍보 비용 이다.

왜냐하면 N개의 도시에 대해 최소 비용인 C원 만큼 고객을 만들어야하기 때문이다.

DP[i] = 돈을 i원 만큼 사용했을 때 최대 확보 고객이라고 한다면

C는 최대 1000이며, 도시를 홍보할 때 드는 비용은 최대 100이다.

100의 돈을 사용했을 때 1명의 고객을 확보할 수 있다면, 100 * 1000인 100000의 크기의 DP 배열이 필요하다.

 

12 2
3 5
1 1

 

위 경우가 입력으로 들어왔다면, 1원부터 X원 까지 최대 고객을 알아봐야한다.

1	2	3	4	5	6	7	8
1	2	5	6	7	10	11	12

위 표처럼 최대 고객이 만들어 진다.

 

점화식을 새워본다면 사용할 수 있는 금액과 입력으로 들어온 홍보 비용 값과 나누어 떨어긴 경우와 

사용할 수 있는 금액과 입력으로 들어온 홍보 비용의 차이가 0보다 클때로 나누어 볼 수 있다.

 

나누어 떨어지는 경우는 홍보 비용을 연속으로 사용할 수 있다는 의미이다.

즉, 입력을 예로 든다면 3의 홍보 비용을 연속으로 2번 사용하여 DP[6]에 2 * 5 을 넣는다는 의미이다.

DP[X] = MAX(이전에 구했던 DP 값, (현재 사용할 금액 / 홍보 비용) * 도시 인원 수)

 

0보다 클때는 홍보 비용을 사용할 수는 있지만 연속으로 사용하는 것이 아니라는 의미이다.

즉, 입력으로 예를 든다면 현재 홍보 비용의 인원 수와 과거에 구한 인원수를 더하는 것이다. DP[7] = DP[6] + 1

DP[X] = MAX(이전에 구했던 DP 값, DP[현재 사용할 금액 - 홍보 비용] + 도시 인원 수)

현재 사용할 금액에서 홍보 비용을 빼는 이유는 DP[7]일 때 3인 경우 6원에서 오는 것이 아닌 4원에서 값을 누적 시켜야 하기 때문이다.

 

#include<iostream>
#include<cstring>
using namespace std;

int C, N;
pair<int,int> arr[21];
int dp[100001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin>> C >> N;
    
    for(int i = 0;i<N;i++)
        cin>>arr[i].first>>arr[i].second;

    
    for(int i = 1;i<=100000;i++){
       for(int j = 0;j<N;j++){
            if(i%arr[j].first == 0){
                dp[i] = max(dp[i], (i/arr[j].first)*arr[j].second);
            }
            if(i-arr[j].first >= 0){
                dp[i] = max(dp[i], dp[i-arr[j].first] + arr[j].second);
            }
       }
       if(C<=dp[i]){
            cout<<i<<'\n';
            break;
       }
    }
    
    
    return 0;
}