문제 링크

문제

풀이

냅색 문제와 유사하다는 생각이 드는 문제였다.
비슷한 방식으로 풀이를 진행했으나 끝에 생각하지 못한 오류가 있어 다른 글들을 참고했다.

주어지는 메모리가 10,000,00이기 때문에 메모리를 기준으로 DP배열을 만들면 시간초과가 날 것이라고 생각했다.

따라서 비용을 기준으로 DP배열을 만들어줬다.
이에 따른 점화식은,

 DP[j] = max(DP[j], DP[j - c[i]] + m[i]);

이다.
배열은 주어지는 cost에서 최대 얼마의 메모리를 사용할 수 있는지를 저장한다.

실수했던 부분은 DP를 진행하면서 수행순서를 잘못 지정해준 것이다.

void calcDP(){
    for(int i = 0; i < N; i++){
        for(int j = c[i]; j < COST_LIMIT; j++){
            DP[j] = max(DP[j], DP[j - c[i]] + m[i]);
        }
    }
}

처음에는 위와 같은 방식으로, j가 증가하는 방식으로 식을 구성했는데 이럴 경우 반복문이 돌면서 이미 갱신되었던 DP[j]가 이후 다시 계산에 사용되는 문제가 있었다.
따라서 DP를 감소시키는 방향으로 식을 구성하여 한번만 계산될 수 있게 수정해주었다.

최종코드

#include <iostream>
#include <algorithm>
#define COST_LIMIT 10001

using namespace std;

int N, M;
int m[100];
int c[100];
int DP[COST_LIMIT];

void input(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i = 0; i < N; i++){
        cin >> m[i];
    }

    for(int i = 0; i < N; i++){
        cin >> c[i];
    }
}

void calcDP(){
    for(int i = 0; i < N; i++){
        for(int j = COST_LIMIT - 1; j >= c[i]; j--){
            DP[j] = max(DP[j], DP[j - c[i]] + m[i]);
        }
    }
}

void findAns(int require_mem){
    for(int i = 0; i < COST_LIMIT; i++){
        if(DP[i] >= require_mem){
            cout << i;
            return;
        }
    }
}

int main(){
    input();

    calcDP();

    findAns(M);

    return 0;
}