[백준 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]);
풀이 요약
- 백준 11066 파일 합치기 문제랑 똑같은 문제다. 더 상세한 풀이 설명은 백준 11066 파일 합치기 포스팅을 참고하자.
- 이 풀이는 python3으로 제출하면 TLE가 뜬다. pypy3이나 node.js로 제출하자.
- 주어진 행렬 N개를 최소 곱셈 횟수로 곱하는 방법은, 행렬 N개를 두 개의 그룹으로 분할하고, 각 그룹을 따로 최소 곱셈 횟수로 곱해준다. 두 그룹의 최소 곱셈 횟수와, 곱셈 후 하나의 행렬로 압축된 두 그룹의 두 행렬에 대한 곱셈 연산 횟수를 더해주면 된다.
- 전체를 두 개의 그룹으로 분할하고, 각 그룹의 최소 곱셈 횟수를 가지고 원래의 전체 그룹의 최소 곱셈 횟수를 구한다는 점에서 분할 정복, 즉 재귀의 구조가 보인다. DP를 적용하면 되는 것이다. 다만 재귀 구조로 top-down 방식을 취하면 시간이 오래 걸리므로 bottom-up 방식으로 풀자.
가장 바깥 for문
은 분할하고 난 그룹 하나의 크기가 1부터 N-1까지인 경우를 다 도는 것이다. 전체 그룹을 두 개의 그룹으로 계속 분할해가는데, 이 때 길이가 N인 그룹의 최소 곱셈 횟수를 구하려면 길이 1~N-1인 그룹의 최소 곱셈 횟수를 활용한다는 것을 알 수 있다. 즉, 길이가 1인 모든 그룹의 최소 곱셈 횟수, 길이가 2인 모든 그룹의 최소 곱셈 횟수, 이 순서로 길이 N 전체 그룹까지 쭉 구해서 DP 리스트에 메모이제이션해주는 것이다.
-
각 그룹 size에 대해, start는 N-size-1까지만 돈다. N-size일 때부터는, end = N-size+size = N이므로 matrix의 인덱스를 넘어가버리기 때문이다.
여기까지가 두 번째 for문이다.
- 이제 matrix의 start부터 end까지 해당하는 그룹의 최소 곱셈 횟수를 구하자. 세 번째 for문을 돌면서, cut을 기준으로 그룹을 분할하는 모든 경우를 돌자. 이게 세 번째 for문이다. 각 단계에서 그룹의 최소 곱셈 횟수는, 분할된 두 그룹의 최소 곱셈 횟수의 합과, 압축되고 난 두 행렬의 곱셈 연산 횟수의 합을 더해준 것이다. 압축되고 난 두 행렬의 곱셈 연산 횟수는, 분할된 첫 번째 그룹의 첫 행렬의 "행"과 마지막 행렬의 "열"과 분할된 두 번째 그룹의 마지막 행렬의 "열"의 곱이다. 이는 행렬의 곱셈을 할줄알면 알 수 있는 사실이다. 문제의 설명에도 적혀있다.
- DP[0][-1]을 출력해주면 끝! 참고로 3중 for문이라 O(N)이다.
배운 점, 어려웠던 점
- 11066 파일 합치기 문제랑 풀이가 똑같아서 쉬웠다.
Author And Source
이 문제에 관하여([백준 11049 파이썬, node.js] 행렬 곱셈 순서 (골드3, DP)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ledcost/백준-11049-파이썬-node.js-행렬-곱셈-순서-골드3-DP저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)