문제

이 문제는 어떻게 dp로 접근할지 고민을 많이 한 문제이다.

문제 링크

문제 접근

  • 나는 dp를 비활성화의 비용 당 최대 메모리 공간으로 했다.
  • 그리고 원소를 하나씩 넣어보면서 dp값을 업데이트 한다.
  • 새로운 원소를 넣으며 업데이트 할때는 뒤에서 부터 업데이트해야 겹치지 않을 수 있다!

코드

#include <cstdio>
#include <cstring>
int N, M, m[101], c[101], dp[10001];
int main(){
    scanf("%d %d", &N, &M);
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < N; i++)scanf("%d", &m[i]);
    for(int i = 0; i < N; i++)scanf("%d", &c[i]);
    for(int i = 0; i < N; i++){
        int cost = c[i];
        for(int j = 10000; j >= cost; j--){
            if(dp[j - cost] == -1)continue;
            if(dp[j - cost] + m[i] > dp[j])dp[j] = dp[j - cost] + m[i];
        }
        if(dp[cost] < m[i])dp[cost] = m[i];
    }
    for(int i = 0; i < 10001; i++){
        if(dp[i] >= M){
            printf("%d", i);
            break;
        }
    }
}