[c++] 7579 앱 (knapsack)

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

7579번: 앱

 

 

노트북 재부팅 5번의 원인이 된 문제

 

이유는..

1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN

이래서 배열을 dp[101][1000000001] ㅋㅋㅋ이렇게 설정했더니 컴퓨터가 바로 종료..

배열을 너무 큰 값으로 설정하면 안된다

 

그냥 비용을 dp 로 설정하면 되는 문제였다.

평소와 거꾸로 생각한다는 느낌으로 i번째 앱까지 걸리는 비용을 j로 두고 메모리를 값으로 !

메모리가 M바이트 이상이어야 하니까 M바이트 이상일 때 j값을 결과값으로 설정한다.

 

 

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

// i번째 앱까지 걸리는 시간

int N, M, sum, res=1e9, memory[101], cost[101], dp[101][10001];

int main() {
    cin >> N >> M;
    for (int i=1; i<=N; i++) {
        cin >> memory[i];
    }
    for (int i=1; i<=N; i++) {
        cin >> cost[i];
        sum += cost[i];
    }
    
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=sum; j++) {
            if (cost[i] <= j) {
                dp[i][j] = max(dp[i-1][j-cost[i]] + memory[i], dp[i-1][j]);
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
            if (dp[i][j] >= M) {
                res = min(res, j);
            }
        }
    }
    
    cout << res << "\n";
}