[백준 7579 파이썬, node.js] 앱 (골드3, DP)

알고리즘 유형 : DP, 냅색
풀이 참고 없이 스스로 풀었나요? : O

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

SOLVE 1

발상의 전환 : 전체 문제를 색다르게 정의하는 풀이

import sys
input = sys.stdin.readline

N, M = [*map(int, input().split())]
resource = [0] + [*map(int, input().split())]
costs = [0] + [*map(int, input().split())]
tmp_col = sum(costs)+1
knapsack = [[0]*(tmp_col) for _ in range(N+1)]

for app in range(1, N+1):
    for cost in range(tmp_col):
        if costs[app] <= cost:
            knapsack[app][cost] = max(resource[app] + knapsack[app-1][cost-costs[app]],
                                     knapsack[app-1][cost])
        else:
            knapsack[app][cost] = knapsack[app-1][cost]

for idx in range(tmp_col):
    if knapsack[-1][idx] >= M:
        print(idx)
        break

SOLVE 2

냅색 알고리즘 정석대로 부분 문제를 정의하고 풀 되, 메모이제이션 배열을 1차원으로 구성하여 메모리 사용을 최소화하는 풀이

"use strict";
const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const resource = [0].concat(input[1].split(" ").map(Number));
const cost = [0].concat(input[2].split(" ").map(Number));
const DP = Array.from({length: M+1}, (v, i) => (-1));
DP[0] = 0;

// 냅색 알고리즘
for (let step=1; step<N+1; step++){
    for (let col=M; col>0; col--){
        // 현재 행(현재 앱 메모리)이 현재 열(확보하려는 메모리)보다 작을 때
        if (resource[step] < col){ 
            if (DP[col] != -1){ // 현재 앱 안 지우고 그 이전의 앱들 지워서 목표 메모리를 채우는 경우가 존재할 때
                DP[col] = Math.min(DP[col], cost[step] + DP[col-resource[step]]);
            }else{ // 목표 메모리를 현재 앱 안 지우고 그 이전의 앱들만으로 지워서 채우는 경우가 존재하지 않을 때
                if (DP[col-resource[step]] != -1){ // 현재 앱을 지우고, 나머지를 그 이전의 앱들을 지워서 채울 수 있을 때
                    DP[col] = cost[step] + DP[col-resource[step]];
                }else{ // 현재 앱을 지우고 나머지를 그 이전의 앱들을 지워 채울 수도 없을 때
                    DP[col] = -1;
                }
            }
        }else{ // 현재 행(현재 앱 메모리)이 현재 열(확보하려는 메모리)보다 클 때
            if (DP[col] != -1){ // 현재 앱 안 지우고 그 이전 앱들만으로 목표 메모리 확보하는 경우가 존재할 때
                DP[col] = Math.min(DP[col], cost[step]);
            }else{ // 현재 앱 안 지우고는 목표 메모리 못 채우는 경우
                DP[col] = cost[step];
            }
        }
    }
}

console.log(DP[M]);

SOLVE 1) 풀이 요약 (발상의 전환 : 전체 문제를 색다르게 정의하는 풀이)

1. 기존에 냅색 알고리즘을 풀던대로라면, 주어진 앱들을 원하는 것만 비활성화할 수 있으므로 이를 행으로 두고, 앱을 어떤 것을 비활성화하느냐에 따라 확보되는 메모리가 달라지므로 이를 열로 두고, 메모이제이션의 원소는 구하는 답인 최소 비용이다.

   이 때 전체 문제는 "1~N번 앱에서 몇 개를 비활성화해서 메모리를 M만큼 확보하는 최소 비용을 구하는 것"이다. 그리고 부분 문제는, i(1<=i<=M)의 메모리를 확보하는 최소 비용이고(열), 더 세분화해서 1번 앱을 대상으로 구하는 경우, 1~2번 앱을, 1~3번 앱을, ..., 1~N번 앱을 대상으로 구하는 경우로 나눌 수 있다.(행)

   그런데 이대로 풀어버리면 주어진 메모리 제한을 초과해버린다.(100*10000000 = 10억, 정수 하나가 4바이트이므로 총 메모리는 40억 바이트 = 4000MB) 물론 SOLVE 2처럼 1차원 메모이제이션 배열을 구성하면 해결할 수 있지만, 풀이가 좀 더 복잡해지기도하고, 시공간 자원을 SOLVE 1보단 많이 먹는다.

   아무튼 이를 해결하기 위해, "전체 문제"를 기존의 냅색 문제를 풀던 패턴과 조금 다르게 설정하면 된다.

   "1~N번 앱에서 비용 한도 M으로 몇 개를 비활성화해서 비울 수 있는 최대 메모리"로 설정한다. 이 때 메모이제이션의 원소는 구하는 답인 최대 메모리이고, 따라서 행은 앱의 메모리들, 열은 비용 한도(1~sum(앱의 비용들))이다.

   그리고 이 때의 최종 답은 DP[-1][-1]이 아니라, 마지막 행, 즉 1~N번 앱에서 비용 한도 i(1<=i<=sum(앱의 비용들))로 확보한 최대 메모리 값들 중에, 비용 한도를 작은 것부터 조회하면서, 처음으로 최대 메모리 값이 문제에서 요구하는 M 이상이 되는 경우, 그 때의 열(비용 한도) 값이다. 그 값이 최소 비용이다.

2. 구현은 기존에 냅색 알고리즘을 구현하던 것과 똑같이 하면 된다. 행과 열, 원소의 대상이 달라진 것 뿐이니까.

   점화식은 knapsack[app][cost] = max(resource[app] + knapsack[app-1][cost-costs[app]], knapsack[app-1][cost]) (if costs[app] <= cost, else knapsack[app][cost] = knapsack[app-1][cost])

   행:앱의 메모리 열:비용 한도	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   -	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
   30	0	0	0	30	30	30	30	30	30	30	30	30	30	30	30	30
   10	10	10	10	40	40	40	40	40	40	40	40	40	40	40	40	40
   20	10	10	10	40	40	40	60	60	60	60	60	60	60	60	60	60
   35	10	10	10	40	40	40	60	60	75	75	75	95	95	95	95	95
   40	10	10	10	40	50	50	60	80	80	85	100	100	115	115	115	135

3. 저 위에 표는 문제에서 주어진 테스트케이스에 대한 것이다. 점화식을 이해하는데 도움이 될 것이다.

   이를 for문을 돌면서 싹 다 구해주고, 마지막 행에서 0열부터 for 돌면서, 최초로 값이 M 이상이 될 때, 그 때의 column이 구하는 최소 비용이다. 왜냐하면, 이 테스트 케이스의 경우 6열이 답인데, 5열까지는 원소가 M보다 작았고, 그보다 비용의 한도가 1 늘어났더니 원소가 M 이상이 되었다. 이 것은 비용 한도가 1이 늘음으로써 비활성화하는 앱이 변경되었고, 비용 한도 1이 늘었기 때문에 가능했던 것이므로 반드시 비용 한도에 딱 맞게 비용을 사용하고 메모리를 M 이상으로 확보하게 된다. 즉, 이 경우의 비용 한도가 곧 최소 비용이다.

SOLVE 2 풀이 요약 (냅색 알고리즘 정석대로 부분 문제를 정의하고 풀 되, 메모이제이션 배열을 1차원으로 구성하여 메모리 사용을 최소화하는 풀이)

1. 우선 정석적인 냅색 알고리즘 풀이를 생각해보자.

   주어진 앱들을 원하는 것만 비활성화할 수 있으므로 이를 행으로 두고, 앱을 어떤 것을 비활성화하느냐에 따라 확보되는 메모리가 달라지므로 이를 열로 두고, 메모이제이션의 원소는 구하는 답인 최소 비용이다.

   이 때 전체 문제는 "1~N번 앱에서 몇 개를 비활성화해서 메모리를 M만큼 확보하는 최소 비용을 구하는 것"이다. 그리고 부분 문제는, i(1<=i<=M)의 메모리를 확보하는 최소 비용이고(열), 더 세분화해서 1번 앱을 대상으로 구하는 경우, 1~2번 앱을, 1~3번 앱을, ..., 1~N번 앱을 대상으로 구하는 경우로 나눌 수 있다.(행)

   점화식은 이 풀이에서는 세우기가 조금 애매하다. 왜 그런지는 설명을 보다보면 이해될 것이다.

   우선 점화식을 대략적으로 세워보면 knapsack[row][col] = min(knapsack[row-1][col], cost[row] + DP[row-1][col-resource[row]])

   그런데 잘 생각해보면, 메모리 30인 앱 하나만으로 메모리 60을 확보하는 경우를 생각해보자. 이는 불가능한 경우이다. 이처럼 최소 비용이 존재하지 않는 경우도 있으므로, 메모이제이션 배열의 0행은 -1으로 초기화하고, 단 0열은 0으로 초기화한다. 메모리 0을 확보하는 앱을 아무것도 안 끄면 되니까 최소 비용은 0이기 때문이다.

   자 이제 점화식을 통해 메모이제이션 배열을 채워나갈건데, 부분 문제. 즉 이전에 구해놨던 원소 중에 -1이 있기 때문에, 조건문 기준이 두 가지이다.

   1) 현재 행에 해당하는 앱의 메모리가 현재 열(목표 확보메모리)보다 작은 경우, 크거나 같은 경우

   2) 이전 행의 값을 조회하는데 그게 -1인 경우와 아닌 경우

   이 두 가지를 적절히 짬뽕시키면 된다.
   이 부분은 코드와 주석을 보는게 더 이해가 쉬울 것 같은데, 혹시 모르니 글로 설명도 해놔야겠다.

   ① 현재 행에 해당하는 앱의 메모리가 현재 열보다 작은 경우에는, 만약 해당 앱을 비활성화한 경우에, 아직 목표 메모리를 확보하지 못했기 때문에 그 이전의 앱들을 통해 더 비워줘야한다.
   1) 이 때, 만약 현재 앱을 놔두고 이전의 앱들로 목표 메모리를 확보하는 경우(DP[row-1][col])이 있다면, DP[row][col]은 이전의 앱들로 목표 메모리 확보하는 최소 비용 DP[row-1][col]과, 현재 앱을 비활성화하고, 남은 메모리를 그 이전의 앱들로 확보하는 최소 비용(cost[row] + DP[row-1]col-resource[row]])의 합이 구하는 값이다.
   2) 만약 현재 앱을 놔두고 이전의 앱들로 목표 메모리를 확보하는 경우가 없다면(DP[row-1][col] = -1), 현재 앱을 무조건 비활성화해야한다. 현재 앱을 비활성화했을 때, 나머지 메모리를 이전의 앱들로 확보하는 경우가 있다면(DP[row-1][col-resource[row]] != -1), 이 값과 현재 앱을 비활성화하는 비용을 합한 값이 구하는 값이고, 만약 그런 경우가 없다면(-1이라면), 현재 앱을 비활성화해도 그 이전의 앱으로 나머지 메모리를 확보할 수 없고, 현재 앱을 놔둬도 그 이전의 앱들로 목표 메모리를 확보할 수 없기 때문에, 이 경우는 최소 비용이 존재하지 않아서 구하는 값은 -1이다.

   ② 크거나 같은 경우에는 현재 앱을 비활성화하면 목표 메모리를 확보하므로, 해당 앱을 비활성화하는 비용과, 해당 앱은 놔두고 그 이전의 앱들을 가지고 목표 메모리를 확보하는 최소 비용 중에 최소값을 취한다.

   만약 현재 앱을 놔두고 그 이전의 앱들만으로 목표 메모리를 확보하는 경우가 존재한다면, DP[row-1][col]과 현재 앱을 비활성화하는 비용 cost[row]중 최소값이 구하는 최소 비용이고, 만약 존재하지 않는다면, 현재 앱을 비활성화하는 경우밖에 없으므로 이 때는 cost[row]이 최소비용이다.

   그런데!! 이렇게 구해놓고나면 알겠지만 최악의 경우에 메모이제이션 배열의 크기가 100*10000000 = 10억, 맨 위에서 설명한대로, 이 때 메모리는 4000MB를 잡아먹는다... 그래서 메모이제이션 배열을 1차원으로 구성하고, N번 for문을 돌면서 계속 덧씌우며 업데이트해주는 방식을 활용함으로써 메모리 사용을 최소화할 것이다.

2. 이제 메모이제이션을 1차원으로 구성하여 메모리 사용을 최소화해보자.

   우선 앞서 설명한대로 구현한 코드를 보자.

"use strict";
const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const resource = [0].concat(input[1].split(" ").map(Number));
const cost = [0].concat(input[2].split(" ").map(Number));
const DP = [];
// 냅색 알고리즘
for (let i=0; i<N+1; i++){
    DP.push(Array.from({length: M+1}, (v, i) => (0)));
}

for (let i=1; i<M+1; i++){
    DP[0][i] = -1;
}

for (let row=1; row<N+1; row++){
    for (let col=1; col<M+1; col++){
        //현재 행(현재 앱 메모리)이 현재 열(확보하려는 메모리)보다 작을 때
        if (resource[row] < col){
            if (DP[row-1][col] != -1){ // 확보 메모리를 현재 앱 안 지우고 그 이전의 앱들 지워서 채우는 경우가 존재할 때
                DP[row][col] = Math.min(DP[row-1][col], cost[row] + DP[row-1][col-resource[row]]);
            }else{ // 확보 메모리를 현재 앱 안 지우고 그 이전의 앱들만으로 지워서 채우는 경우가 존재하지 않을 때
                if (DP[row-1][col-resource[row]] != -1){ // 현재 앱을 지우고, 나머지를 그 이전의 앱들을 지워서 채울 수 있을 때
                    DP[row][col] = cost[row] + DP[row-1][col-resource[row]];
                }else{ // 현재 앱을 지우고 나머지를 그 이전의 앱들을 지워 채울 수도 없을 때
                    DP[row][col] = -1;
                }
            }
        }else{ // 현재 행(현재 앱 메모리)이 현재 열(확보하려는 메모리)보다 클 때
            if (DP[row-1][col] != -1){
                DP[row][col] = Math.min(DP[row-1][col], cost[row]);
            }else{ // 현재 앱 안 지우고는 확보 메모리 못 채우는 경우
                DP[row][col] = cost[row];
            }
        }
    }
}

for (let i=0; i<DP.length; i++){
    console.log(DP[i].join(" "));
}

console.log(DP[N][M]);

• DP[row][col]에 값을 할당하는 부분들만 봐보자. row-1의 값들을 활용하는 것을 볼 수 있다. 즉, 1행의 값을 쭉 구하고, 그 다음 2행의 값을 구할 때, 2행을 굳이 만들지말고, 1행에 원래 있던 값을 가지고, 2행에 해당하는 값을 갱신해서 덧씌워가도 되는 것이다. 이 때, DP[row-1]col-resource[row]]처럼, 이전 행 row-1에서, 현재 열보다 작은 열의 값을 활용하는 경우가 있기 때문에, 덧씌우는 방향은 오른쪽 열에서부터 진행해야한다.

  for문의 조건식과 실행문들을 약간씩 수정해주면 구현은 쉽게 끝!
  이 후 마지막 열을 출력해주면 된다.

배운 점, 어려웠던 점

• 냅색 알고리즘 정석대로 풀려니 정말 엄청 오랜 시간이 걸렸다... 값을 구할 때마다 고려해야 할 조건이 까다로워서 디버깅하는데 오래 걸렸고, 거기에 메모리 최적화까지 해야하니 오래 걸릴수밖에...

• 이런 식으로 발상의 전환을 통해 전체 문제를 색다르게 정의하면, 메모리 최적화와 더불어 점화식을 세우는 것과 구현의 난이도가 더 쉬워지는 경험을 할 수 있어 유익한 문제였다.