백준 7579 앱 - C++, 배낭 문제

7579번: 앱

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, sum = 0;
int mem[10001];
int abyte[101];
int cost[101];

int main(){
    scanf("%d %d", &n ,&m);

    for(int i = 0; i < n; i++)
        scanf("%d", &abyte[i]);

    for(int i = 0; i < n; i++){
        scanf("%d", &cost[i]);
        sum += cost[i];
    }
    
    for(int i = 0; i < n; i++){
        for(int j = sum; j >= cost[i]; j--){
            mem[j] = max(mem[j], mem[j-cost[i]] + abyte[i]);
        }
    }
    for(int i = 0; i < 10001; i++){
        if(mem[i] >= m){
            printf("%d\n", i);
            break;
        }
    }
    
}

---

 기존 배낭 문제와 비슷한 접근을 했지만 입력이 쌍으로 순차 입력이 아니라 각 항목을 입력받는 방식이라 배열이 2개 필요했습니다.

 입력을 다 받고 나서는

mem[j] = max(mem[j], mem[j-cost[i]] + abyte[i]);

 이걸 통해서 한번씩 배낭 문제를 풀이하면 됩니다. 메모리 j 비용일때 i번째를 활성화한것, 활성화하지 않은게 더 많이 사용하는지 알아보게 됩니다.