[ 백준 ] 1106번 - 호텔 (C++)

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

1106번: 호텔

 

 

[ 문제풀이 ]

 

1. 홍보 비용과 효과를 입력받고, pair<int, int> arr 배열에 저장합니다.

 

2. cus[ i ] 배열을 만들어 i명의 손님을 받았을 때 최소 비용을 저장합니다.

 

3. cus[ j + arr[ i ].second ]  = min(cus[ j + arr[ i ].second ], cus[ j ] + arr[ i ].first) 의 점화식을 통해 배열을 갱신해 줍니다.

 

4. j의 값이 C보다 크거나 같을 때 최솟값을 ans에 저장합니다.

 

5. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int C, N;
pair<int, int> arr[20];
int cus[1111];
int ans = 987654321;
 
int main()
{
    scanf("%d %d", &C, &N);
 
    fill(cus+1, cus + 1111, 987654321);
 
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arr[i].first, &arr[i].second);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < C; j++) {
            cus[j + arr[i].second] = min(cus[j + arr[i].second], cus[j] + arr[i].first);
 
            if (j + arr[i].second >= C) {
                ans = min(ans, cus[j + arr[i].second]);
            }
        }
    }
 
    printf("%d", ans);
}