[백준 7579번] [동적 계획법] 앱

좀 애먹기는 했다.. 처음에는 백준 12865번 소풍처럼 메모리를 기준으로 구획하려고 하였는데 메모리 초과가 되었다.

생각해보면 당연한 결과인게

dp[10000000]을 하고 숫자를 넣게되면 128mb는 금방 넘게 된다. 그래서 다양한 풀이방법을 고안하게 되었고 해당 접근 방법은 다음과 같다.

 

메모리를 쓸건지 말건지 2가지 케이스가 존재한다. 그리고 이전에 메모리 상태에 따라서 사용 여부의 효율성이 결정난다.
즉 이러한 측면에서 부분문제를 해결함으로써 전체 문제의 답에 접근하는 최적 부분 구조(Optimal substructure) 형태임을 파악했어야 한다. 다만, 탐욕적으로 선택하는 방향은 아니므로 그리디가 아닌 DP(동적 계획법)으로 접근했어야 한다.

다만, 착각하기 쉬운 지점이
총 앱의 갯수가 N이고 각 N에 대해서 쓸건지 말건지를 결정하는 과정에서 경우의 수가 2이므로, 요구되는 Time-complexity가
O(2^N)이라고 생각하기 쉽다.
하지만, 잘 생각해보면 비용을 기준으로 분류하였을 때 비용이 최대 100이므로, 최대 상한은 100 * 100 = 10000밖에 안된다.

즉 중간에 겹치는 것이 상당히 많다는 것을 추측할 수 있다. 따라서 이 부분은 DP를 활용해서 계산해주면 시간 복잡도에서 이득을 볼 수 있다.

1. DP를 어떤 것을 기준으로 구획할 것인지 설정해야 한다.
가장 먼저 생각할 수 있는 기준은 사용한 메모리이다. 하지만, 이 방법의 경우는 공간복잡도가 매우 높아서 주어진 128mb를 금방 상회하게 된다.
그러면 다른 방법이 무엇이 있는지를 고민해보면 비용을 기준으로 구획하면 된다는 사실을 쉽게 파악할 수 있다.

따라서 dp[i][j] 를 i번째 index까지 고려하였을 때 j만큼의 cost를 사용하였을 때 최대로 줄일 수 있는 memory라 정의하면 된다.

2. 점화식을 세우고 관계식을 확보한다.
기본적으로 점화식은
dp[index][j + cost[index]] = max(dp[index][j + cost[index]], dp[index - 1][j] + memory[index]) 이다.
(만약 index가 0인 경우는 DP에 추가만 시켜줌) 

3. Base Case 고려한다.
일단 함수에서 전체적인 방향성이 index를 키워나가면서 DP를 활용할 것이므로
index가 Boundary안에 존재하는지 확인해주면 된다. 또한 index가 0인 경우는 이전 인덱스를 고려하지 말고 그냥 dp에 추가만 해주면 되는 형태이므로 따로 빼서 정의해두도록 하자.

위의 방법을 활용하여 코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int app_num, delete_memory;
int memory[101];
int cost[101];

int dp[100][10001];

void dp_check(int index){
    if(index >= app_num) return;
    if(index == 0){
        dp[index][cost[index]] = memory[index];
    }
    else{
        dp[index][cost[index]] = max(dp[index][cost[index]], memory[index]);
        for(int i = 0; i < 10001; i++){
            if(dp[index - 1][i] != 0){
                dp[index][i + cost[index]] = max(dp[index][i + cost[index]], dp[index - 1][i] + memory[index]);
                dp[index][i] = max(dp[index][i], dp[index - 1][i]);
            }
        }
    }   
    dp_check(index + 1);
    return;
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> app_num >> delete_memory;

    for(int i = 0; i < app_num; i++){
        int temp;
        cin >> temp;
        memory[i] = temp;
    }

    for(int i = 0; i < app_num; i++){
        int temp;
        cin >> temp;
        cost[i] = temp;
    } // Data_store

    memset(dp, 0, sizeof(dp));

    dp_check(0);

    for(int i = 0; i < 10001; i++){
        if(dp[app_num - 1][i] >= delete_memory){
            cout << i << "\n";
            return 0;
        }
    }
}

문제를 풀어보니, DP의 경우에는 푸는 것 자체가 중요한 것이 아니라 어떠한 방향성을 기준으로 DP를 잡고

점화식을 어떻게 세울 수 있을 것인가에 대한 태도가 가장 중요하다.

 

해당 내용을 중심으로 많이 복습하도록 하자.