백준 1106 호텔 C++

2차원 dp로 할려다가, 기존의 배낭문제처럼 최댓값을 이어서 받는 것은 고객 수의 idx가 배수가 아닐 경우, 문제가 생겨서 1차원 dp로 해결하였다.
주석을 상세히 다시 달아보았다.

적어도 c명 이상이므로, 도시당 고객의 수가 최대 100명이다. 그러므로 c+100 명 이상까지 계산해야 한다.

반례

100 3
7 12
20 30
30 60

답 : 57

답

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int c,n;
    cin>>c>>n;
    vector<pair<int,int>> v(n); // 고객 수, 비용
    for(int i=0;i<n;++i){
        cin>>v[i].second>>v[i].first;
    }
    sort(v.begin(),v.end());
    vector<int> dp(c+120,987654321);
    dp[0]=0;
    for(int i=0;i<n;++i){
        dp[v[i].first]=min(dp[v[i].first],v[i].second); // dp의 초기값 세팅
    }
    // 1차원 dp 계산
    for(int i=1;i<=c+100;++i){
        for(int j=0;j<=i;++j){
            dp[i]=min(dp[i],dp[i-j]+dp[j]);
        }
    }
    int ans=dp[c];
    for(int i=c;i<=c+100;++i){
        ans=min(ans,dp[i]);.  
    }
    cout<<ans;
}