백준 1106 호텔 (C++)

1106번: 호텔

배낭 문제를 이용한 문제이다. 비용을 나타내는 dp[]를 이용하여 문제를 해결하였다. 배열의 최댓값은 100 * 1000으로 100000으로 설정하였다. 반복문을 돌면서 도시 하나씩 dp에 현재 비용에 해당하는 위치에 비교하며 값을 저장해주었다. 그 후 1원부터 다시 반복문을 돌며 C보다 큰 dp값이 나올 경우 출력해주었다.
배낭 문제를 많이 안 풀어봐서 그런지 생각보다 햇갈리는 문제였다. 처음 문제를 봤을 때 단순히 배낭 문제를 이용하면 된다고 생각하여 dp를 2차원으로 지정하고 문제를 풀어보려 했는데 이럴 필요없이 1차원으로 가능했다는 점이 인상적이었다. 배낭 문제라고 2차원 배열에 매몰되지 않고 여러 방식이 있다는 점을 인지해야 겠다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int C, N;
vector<pair<int, int>> v;
int dp[100001];

void solution() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 100000; j++) {
            int cost = v[i].first;
            int man = v[i].second;

            if (j - cost >= 0) {
                dp[j] = max(dp[j], dp[j - cost] + man);
            }
        }
    }

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> C >> N;

    v.push_back({ 0,0 });
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ a,b });
    }

    solution();

    return 0;
}