백준 1106

1106번: 호텔

 

풀이

  처음 보는 유형의 dp. dp[i]의 정의를 사람을 i명 이상 구할 때 드는 최소비용이라 정의하자. 그러면 어떤 홍보 수단이 3원에 5명을 구할 수 있다고 가정할 때 dp[i]의 최솟값은 dp[i - 5] + 3, dp[i - 4] + 3, ... , dp[i - 1] + 3 중 하나가 된다. 모든 홍보 수단에 대해 최솟값을 찾아 업데이트 하면 답을 구할 수 있다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int c, n;
    cin >> c >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    
    int dp[c + 1];
    dp[0] = 0;
    for (int i = 1; i <= c; i++) {
        dp[i] = INF;
        for (auto j : a) {
            for (int k = max(i - j.second, 0); k <= i - 1; k++) {
                dp[i] = min(dp[i], dp[k] + j.first);
            }
        }
    }
    cout << dp[c];
    return 0;
}