16493번 최대 페이지 수

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

 

냅색

 

#include<bits/stdc++.h>

using namespace std;

int N, M, cache[201][21];
vector<pair<int, int> > v;

int ks(int goal, int idx)
{
    if (idx == M) {
        return 0;
    }

    int& ret = cache[goal][idx];

    if (ret != -1) return ret;

    ret = ks(goal, idx + 1);
    if (goal - v[idx].first >= 0) {
        ret = max(ret, ks(goal - v[idx].first, idx + 1) + v[idx].second);
    }

    return ret;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);
    memset(cache, -1, sizeof(cache));

    scanf("%d %d", &N, &M);

    int d, p;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &d, &p);
        v.push_back({ d, p });
    }

    printf("%d\n", ks(N, 0));

    return 0;
}