[BOJ/백준][Gold5] 1106 : 호텔 (C++)

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

1106번: 호텔

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[c] : 고객을 적어도 c명 늘이기 위해 투자해야하는 최솟값
배낭문제 응용입니다.
0~N-1까지 반복문을 돌려주면서 i번 도시까지 홍보할때의 최솟값을 DP 배열에 순차적으로 저장해주면 됩니다.

 

 

#include <cstdio>
#include <algorithm>
using namespace std;
int C,N,p[20],cost[20],dp[1001],inf=9e8;
int main(){
    scanf("%d%d",&C,&N);
    for(int i=0;i<N;i++) scanf("%d%d",&cost[i],&p[i]);
    for(int i=1;i<=C;i++) dp[i]=inf;
    for(int i=0;i<N;i++){
        for(int j=1;j<=C;j++){
            for(int k=1;;k++){
                int v=0;
                if(j-p[i]*k>=0) v=dp[j-p[i]*k];
                if(dp[j] > v+cost[i]*k) dp[j] = v+cost[i]*k;
                else break;
            }
        }
    }
    printf("%d",dp[C]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1106.cpp