[백준][C++] 7579번: 앱 <216>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

7579번: 앱

생각의 흐름

이번 문제는 유명한 KnapSack 문제이다. 해당 알고리즘에 대한 설명을 다음과 같이 정리해 두었다.

[알고리즘] Knapsack Problem

이번 문제에서는 cost를 최소화 시키는 것을 목표로 하면서 해결해야 한다.

int DP[i][j] : 비용이 j일때 앱 1,2,...,i를 통해 얻을 수 있는 최대의 메모리

i번의 앱까지 모든 탐색을 끝냈을 때 dp[i][j]의 값은 j의 비용으로 얻을 수 있는 최대의 메모리 크기입니다.

즉, 사용할 수 있는 j의 비용이 늘어날수록 얻을 수 있는 메모리도 늘어날 텐데 처음으로 M을 넘는 j값이 바로 이 문제의 정답이 됩니다.

 

case 1) i번 앱을 선택하지 않는 경우

DP[i][j] = DP[i-1][j] 가 된다. i번째 까지의 최적해 집합은 i를 포함하지 않는 DP[i-1][j]와 동일하다.

 

case 2) i번 앱을 선택하는 경우

DP[i][j] = i번 앱 종료 메모리 + DP[i-1][j-[i번 앱 재부팅 비용]] 이 된다.

 

추가로, 사용 가능한 최대 비용은 100*100 으로 배열을 만들때 10001로 잡아주게 되었습니다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 101

int N, M;
int useMemory[MAX];
int restartTime[MAX];
int DP[MAX][10001]; // i번째 앱까지 중 j코스트로 얻을 수 있는 최대의 메모리

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

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

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

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= sum; j++) {
            if (restartTime[i] <= j) {
                DP[i][j] = max(DP[i - 1][j - restartTime[i]] + useMemory[i], DP[i - 1][j]);
            } else {
                DP[i][j] = DP[i - 1][j];
            }
        }
    }

    for (int i = 0; i <= sum; i++) {
        if (DP[N][i] >= M) {
            cout << i;
            break;
        }
    }

    return 0;
}