백준 1106 호텔

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

1106번: 호텔

#include <iostream>
#include <vector>

using namespace std;

//dp[i]: i원으로 얻을 수 있는 최대 고객
int dp[100001];

int main() {

    int c, n;

    cin >> c >> n;
    vector<pair<int, int>> ad(n + 1);       //{비용, 이득}


    for (int i = 1; i <= n; i++) {
        cin >> ad[i].first >> ad[i].second;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = ad[i].first; j <= 100000; j++) {
            dp[j] = max(dp[j], dp[j - ad[i].first] + ad[i].second);
        }
    }

    for (int i = 1; i <= 100000; i++) {
        if (dp[i] >= c) {
            cout << i;
            break;
        }
    }


    return 0;
}

 

dp[i]: i원으로 얻을 수 있는 최대 고객

최대 고객이 1000명이고, 그런 도시가 100개까지 존재하기 때문에 100,000개의 dp 배열을 선언한다.

 

 

dp[j]=max(dp[j], dp[j-ad[i].first]+ad[i].second);

j원으로 얻을 수 있는 고객은 현재 고객과 해당 비용을 제출하였을 때의 고객을 비교하여 최댓값을 뽑으면 점화식이 완성된다.

 

if(dp[i]>=c) cout<<i;

이 문제는 고객을 c명 유치하기 위해 필요한 최소 금액이다. 즉 i원으로 유치할 수 있는 고객이 처음으로 c명이 넘어가면 그 값을 출력하면 된다.