[BOJ] 1106번 : 호텔 C++ 풀이

간단한 다이나믹 프로그래밍 문제이다.
각 도시별로 [ 홍보 비용, 고객의 수 ] 정보가 주어진다. 이때 최소 C명을 모으기 위해 필요한 최소 비용을 구하라고 한다. 단, 도시별로 여러번 홍보할 수 있다.

DP[i][j] = i번째 도시까지 j명을 모으기 위한 최소 홍보 비용이라고 정의하자.
그러면 점화식을 도출할 수 있는데, j가 i번째 사람의 고객의 수보다 크거나 같을때 DP[i][j] = DP[i][j-고객의 수] + 홍보 비용이 된다.

그리고 j가 i번째 사람의 고객의 수보다 작다면, DP[i][j] = DP[i-1][j]가 된다. 이를 2중 for문으로 구해주면 된다.

주의 해야할점은 '최소한 C명'이 되는 비용을 구하는 것이다. 따라서 j의 범위는 최댓값인 1100까지 잡고 점화식을 돌려야 한다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
int N, C, DP[21][1110];
vector<pii> v;

void init() {
    memset(DP, MINF, sizeof(DP));
    cin >> C >> N;
    v.push_back({0, 0});
    for (int i=1; i<=N; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    int answer = 1e9;
    for (int i=1; i<=N; i++) {
        DP[i][0] = 0;
        int x = v[i].X, y = v[i].Y;
        for (int j=1; j<=1100; j++) {
            if (j >= y) {
                DP[i][j] = DP[i][j-y] + x;
            } 
            DP[i][j] = min(DP[i][j], DP[i-1][j]);
        }
        for (int j=C; j<=1100; j++) {
            answer = min(answer, DP[i][j]);
        }
    }
    cout << answer << '\n';
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}