호텔 C++ - 백준 1106

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

dp 문제.

범위 체크, 다른 도시여도 같은 지불값이 들어올 수 있다는 것을

인지해야 되는 문제.

문제 접근

c의 범위가 1000이하의 자연수이고,

고객 유치 가격과 얻는 고객의 수가 100이하 자연수이기 때문에,

최대 100000원을 지불해야 가능한 경우가 있다.

이 점을 유의하여 가격을 1~100000원까지 지불하는 경우를 탐색하여

가능한지 확인하고, 가능하다면 고객의 수를 더해주었다.

코드는 다음과 같다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int c,n,ans=0; cin >> c >> n;
    pair<int, int> arr[20];
    int dp[100001]; fill(dp+1,dp+100001,0);
    for(int i=0;i<n;i++){cin >> arr[i].first >> arr[i].second;dp[arr[i].first]=max(dp[arr[i].first],arr[i].second);}
    for(int i=1;i<=100000;i++){
        for(int j=0;j<n;j++) if(i-arr[j].first>0 && dp[i-arr[j].first]>0) dp[i]=max(dp[i],dp[i-arr[j].first]+arr[j].second);
        if(dp[i]>=c){ans=i;break;}
    }
    cout << ans;
    return 0;
}