[백준] 12865 평범한 배낭

정말 평범한 문제다

평범하게 아는대로 냅색을 하면 풀린다

근데 잘 푼 사람들보니까 나랑 메모리가 20배는 차이난다..!

1차dp로 풀었던데 좀 봐야겠다 ㅎㅎ

내가 푼 방식은

가방을 1~N까지 보며 max(선택 O, 선택 X) 를 보며 최대값을 찾았다

소소코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int d[111][111111];
int w[111], v[111];
int n, k;
int go(int pos, int sum) {
    if (sum < 0 ) return -987654321;
    if (sum == 0 || pos==n) return 0;
    int&ret = d[pos][sum];
    if (ret != -1) return ret;
    ret = 0;
    return ret = max(go(pos + 1, sum - w[pos]) + v[pos], go(pos + 1, sum));
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf(" %d %d", &w[i], &v[i]);
    printf("%d\n", go(0, k));
}