[백준 11049 파이썬, node.js] 행렬 곱셈 순서 (골드3, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
DP = [[0]*N for _ in range(N)]

# 분할된 그룹의 크기를 1부터 N-1까지 돎
for size in range(1, N):
	# 크기 size인 그룹의 모든 경우의 수 돎
    for start in range(N - size):
        end = start + size
        
        # 어떤 그룹의 최소 곱셈 횟수는 분할한 두 그룹의 최소 곱셈 횟수 + 각 그룹의 곱셈 다 끝나고 남은 행렬끼리의 곱셈 횟수
        result = float("inf")
        for cut in range(start, end):
            result = min(result, DP[start][cut] + DP[cut+1][end] +
                        matrix[start][0]*matrix[cut][1]*matrix[end][1])
        DP[start][end] = result

print(DP[0][-1])

소스 코드(node.js)

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

const N = Number(input[0]);
const matrix = [];
for (let i=1; i<N+1; i++){
    matrix.push(input[i].split(" ").map(Number));
}

const DP = [];
for (let i=0; i<N; i++){
    DP.push([]);
    for (let j=0; j<N; j++){
        DP[i].push(0);
    }
}

for (let size=1; size<N; size++){
    for (let start=0; start<N-size; start++){
        const end = start + size;
        
        let result = Infinity;
        for (let cut=start; cut<end; cut++){
            result = Math.min(result, DP[start][cut] + DP[cut+1][end] +
                              matrix[start][0]*matrix[cut][1]*matrix[end][1]);
        }
        DP[start][end] = result;
    }
}

console.log(DP[0][N-1]);

풀이 요약

1. 백준 11066 파일 합치기 문제랑 똑같은 문제다. 더 상세한 풀이 설명은 백준 11066 파일 합치기 포스팅을 참고하자.

2. 이 풀이는 python3으로 제출하면 TLE가 뜬다. pypy3이나 node.js로 제출하자.

3. 주어진 행렬 N개를 최소 곱셈 횟수로 곱하는 방법은, 행렬 N개를 두 개의 그룹으로 분할하고, 각 그룹을 따로 최소 곱셈 횟수로 곱해준다. 두 그룹의 최소 곱셈 횟수와, 곱셈 후 하나의 행렬로 압축된 두 그룹의 두 행렬에 대한 곱셈 연산 횟수를 더해주면 된다.

4. 전체를 두 개의 그룹으로 분할하고, 각 그룹의 최소 곱셈 횟수를 가지고 원래의 전체 그룹의 최소 곱셈 횟수를 구한다는 점에서 분할 정복, 즉 재귀의 구조가 보인다. DP를 적용하면 되는 것이다. 다만 재귀 구조로 top-down 방식을 취하면 시간이 오래 걸리므로 bottom-up 방식으로 풀자.

5. 가장 바깥 for문은 분할하고 난 그룹 하나의 크기가 1부터 N-1까지인 경우를 다 도는 것이다. 전체 그룹을 두 개의 그룹으로 계속 분할해가는데, 이 때 길이가 N인 그룹의 최소 곱셈 횟수를 구하려면 길이 1~N-1인 그룹의 최소 곱셈 횟수를 활용한다는 것을 알 수 있다. 즉, 길이가 1인 모든 그룹의 최소 곱셈 횟수, 길이가 2인 모든 그룹의 최소 곱셈 횟수, 이 순서로 길이 N 전체 그룹까지 쭉 구해서 DP 리스트에 메모이제이션해주는 것이다.

6. 각 그룹 size에 대해, start는 N-size-1까지만 돈다. N-size일 때부터는, end = N-size+size = N이므로 matrix의 인덱스를 넘어가버리기 때문이다.

   여기까지가 두 번째 for문이다.

7. 이제 matrix의 start부터 end까지 해당하는 그룹의 최소 곱셈 횟수를 구하자. 세 번째 for문을 돌면서, cut을 기준으로 그룹을 분할하는 모든 경우를 돌자. 이게 세 번째 for문이다. 각 단계에서 그룹의 최소 곱셈 횟수는, 분할된 두 그룹의 최소 곱셈 횟수의 합과, 압축되고 난 두 행렬의 곱셈 연산 횟수의 합을 더해준 것이다. 압축되고 난 두 행렬의 곱셈 연산 횟수는, 분할된 첫 번째 그룹의 첫 행렬의 "행"과 마지막 행렬의 "열"과 분할된 두 번째 그룹의 마지막 행렬의 "열"의 곱이다. 이는 행렬의 곱셈을 할줄알면 알 수 있는 사실이다. 문제의 설명에도 적혀있다.

8. DP[0][-1]을 출력해주면 끝! 참고로 3중 for문이라 O(N$^3$)이다.

배운 점, 어려웠던 점

• 11066 파일 합치기 문제랑 풀이가 똑같아서 쉬웠다.