호텔(BOJ 1106)

문제

이미지 클릭

문제 설명

• c와 n이 각각 주어진다.

c: 모아야 하는 고객의 최소수
n: 도시의 개수

• c명 이상의 고객을 모으기 위해서 n개의 도시에 정수배만큼을 투자하여서 최소한의 비용으로 광고를 해야 한다.

ex)
c=12이고, n=2이고
1번 도시: 3을 투자해서 5명의 고객을 모을 수 있음
2번 도시: 1을 투자해서 1명의 고객을 모을 수 있음

이 경우에는 1번 도시에 6원을 투자해서 10명을 모으고, 2번 도시에 2원을 투자해서 2명을 모으는 것이 최고의 선택이다.

문제 해설

• dp

일반적으로 배낭 문제를 적용하면 다른 문제와 비슷하게 해결할 수 있다.

int cost=i.first, customer=i.second;
            for(int j=customer;j<=c+100;j++){
                  if(dp[j-customer]!=INF){
                        dp[j]=min(dp[j], dp[j-customer]+cost);
                  }
            }​

위처럼 문제를 푼다면 쉽게 해결할 수 있다.

cf) customer~c+100을 탐색해 주는 이유
c가 최소의 손님의 수이고, c를 넘어가는 경우가 더 저렴한 비용으로 광고를 할 수도 있기 때문에 customer부터 c+100(굳이 100이 아니라 어느 정도 큰 수를 더해주면 됨)을 탐색해 준다.

최종 코드

#include<bits/stdc++.h>
#define INF 1e9+7
using namespace std;
int c,n;
vector<pair<int,int>> v;
int dp[2005];
int main(){
      ios::sync_with_stdio(0);cin.tie(0);
      cin>>c>>n;
      for(int i=1;i<=n;i++) {
            int x, y;
            cin>>x>>y;
            v.push_back({x,y});
      }
      fill(dp,dp+2004,INF);
      dp[0]=0;
      for(auto i:v){
            int cost=i.first, customer=i.second;
            for(int j=customer;j<=c+100;j++){
                  if(dp[j-customer]!=INF){
                        dp[j]=min(dp[j], dp[j-customer]+cost);
                  }
            }
      }
      int ans=INF;
      for(int i=c;i<=c+100;i++) ans=min(ans,dp[i]);
      cout<<ans;
}

이미지 클릭