[백준 1106번] 호텔 (C++)

문제링크 : https://www.acmicpc.net/problem/1106

1106번: 호텔

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<pii>v;
int dp[100001];
int result = MAX;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int C, N;
    cin >> C >> N;
    for(int i=0; i<N; i++)
    {
        int cost, num;
        cin >> cost >> num;
        v.push_back({cost, num});
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<100001; j++)
        {
            if(j-v[i].first >=0) dp[j] = max(dp[j], dp[j-v[i].first] + v[i].second);
            if(dp[j]>=C) result = min(result, j); //최소 비용 저장
        }
    }
    cout << result;

    return 0;
}

기본적인 DP 배낭 문제이다.

dp를 선언할때 최대 비용인 1000*100만큼의 크기를 선언해준다.

 

이후 점화식은 DP 배낭 문제의 기본적인 점화식이고,

그렇게 저장한 dp[j]의 값이 C이상 일때의 최소값을 따로 저장하여 출력해주면 된다.