14728번 벼락치기

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

 

 

냅색 문제이다.

 

 

 

#include<bits/stdc++.h>

using namespace std;

int N, T, cache[10001][101];
vector<pair<int, int> > v;

int ks(int T, int idx)
{
    if (idx == N) {
        return 0;
    }

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

    if (ret != -1) return ret;

    ret = 0;

    // 우선 현재 순서를 건너 뛰어본다.
    ret = max(ret, ks(T, idx + 1));
    
    // 알맞은 조건 하에 현재 순서를 진행한다.
    if (T - v[idx].first >= 0) {
        // 비교
        ret = max(ret, ks(T - 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, &T);

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

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

    return 0;
}