[백준 11049번] 행렬 곱셈 순서

문제 링크: 11049번 행렬 곱셈 순서

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

 

일단 고등학교 때 배운, 행렬에 대한 간단한 성질들을 미리 적어둔다...

 

1. 행렬의 곱셈 연산은 교환법칙이 성립하지 않는다.

2. n×m 행렬과 m×l 행렬에 대한 곱셈 연산을 수행하면 그 결과는 n×l 행렬이다.

→ n×m 행렬과, m×l 행렬과, ...,  l×k 행렬에 대한 곱셈 연산을 수행하면 그 결과는 n×k 행렬이다.

3. n×m 행렬과 m×l행렬에 대해 곱셈 연산을 수행하는 데에 필요한 연산의 수는 n×m×l이다.

→ A×B = C라 할 때 C₀₀ 하나를 구하기 위해 A₀₀B₀₀ + A₀₁B₁₀ + A₀₂B₂₀ + ... + A_0mB_m0의 계산(m번)을 수행해야 하며 C의 원소는 n×l개인 점을 상기

 

뭔가 BOJ 11066 파일 합치기가 떠오르는 문제이다. DP의 냄새가 난다... 조금 더 논리다운 논리를 펼치자면, 브루트포스로 모든 경우를 탐색해본다고 할 때, 특정 구간 내의 최소 비용을 여러 번 계산해야 하며(overlapping subproblems), 어떤 구간 내의 최소 비용은 외부에 몇 개의 행렬이 왼쪽이나 오른쪽에서 곱해지더라도 영향을 받지 않기(optimal substructure) 때문이다.

 

그렇다면 다음의 예시에서, 2개 행렬부터 시작해서 하나씩 추가시켜나가보자.

 

3×2 , 2×5 , 5×4 , 4×10 , 10×3 , 3×9 , 9×7 , 7×6

 

[1, 2]의 구간을 본다면?

[1, 2] = 3×2×5 = 30

[1, 3]의 구간을 본다면?

[1, 3] = min([1, 2]×5×4, 3×2×[2, 3])

[1, 4]의 구간을 본다면?

[1, 4] = min(3×2×[2, 4], [1, 2]×5×[3, 4], [1, 3]×4×10)

 

이렇게 생각하다보면, 우리는 [1, x]뿐만 아니라 [x, y]의 구간에 대해서 모두 memoization이 필요하다는 것을 알 수 있다(루비1 문제가 있는 것을 보아 아닐 수도 있는데 일단 내 머릿속에선 무조건 필요하다). 그렇다면, (마침 범위도 500이니) 2차원 DP를 이용하면 어떨까?

 

A1	A2	A3	A4	A5	A6	A7
r1 × c1	c1 × c2	c2 × c3	c3 × c4	c4 × c5	c5 × c6	c6 × c7

 

무작정 예시를 들고자 하니 생각보다 쉬운 일은 아니다.

 

DP[1][1] = DP[2][2] = DP[3][3] = ... = 0
DP[1][2] = r₁×c₁×c₂, DP[2][3] = r₂×c₂×c₃, ..., DP[i][i+1] = r_i×c_i×c_i+1
DP[1][3] = min(A₁×A₂ 이후 A_1×2×A₃을 계산하는 비용, A₂×A₃ 이후 A₁×A_2×3을 계산하는 비용)
...
DP[2][6] = min(여기에 들어갈 게 너무 복잡하기 때문)

 

그런데 이 복잡해 보이는 것은, 사실 생각을 조금만 더 해보면 그다지 복잡하지 않다.

 

<그림 1>

 

<그림 2>

 

DP[2][6] = min(

  ①DP[2][5] + DP[6][6] + r2×c5×c6,

  ②DP[2][4] + DP[5][6] + r2×c4×c6,

  ③DP[2][3] + DP[4][6] + r2×c3×c6,

  ④DP[2][2] + DP[3][6] + r2×c2×c6

)

 

처음에 DP라고 생각했던 것에 집중하여, 각 경우에서 중복되는 계산 과정을 없애고자 하다보면 이런 결과를 얻을 수 있다. 위 DP[2][6]은 A2×A3×...×A6을 하는 과정에서의 최소 연산 수이다. 이를 구하는 과정에서 ①을 예로 들면, A2~A5를 먼저 곱하고(A2×A3 -> A23×A4 -> A234×A5일 수도 있고 A4×A5 -> A3×A45 -> A2×A345일 수도 있고, ... 이걸 모두 고려하여 미리 DP[2][5]를 구해두었기에, <그림 1>과 같이, 한 번만에 고려할 수 있다는 것) 그 후에 A2345에다가 A6을 곱할 때의 연산 수를 구한 것이다. 이 때 A2~A5에 대해 곱셈 연산을 수행하는 순서가 어떻게 되었든, 이미 모든 경우를 고려하여 최소 비용이 이미 구해져있을 것(DP[2][5])이고, 해당 결과(A2×A3×A4×A5 = r2×c5 행렬)에 A6을 곱할 때의 비용을 더한 것이다.

 

한편 이 과정에서 긴 구간의 최소 연산 수를 구하기 위해서는 보다 짧은 구간의 최소 연산 수가 필요하므로, 길이를 1부터 시작해서 증가시켜가면서 DP 배열을 채워나가주면 된다.

 

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

class Matrix {
​​​​int r;
​​​​int c;

​​​​Matrix(int r, int c) {
​​​​​​​​this.r = r;
​​​​​​​​this.c = c;
​​​​}
}

public class Main {
​​​​static int n;
​​​​static Matrix[] arr = new Matrix[501];
​​​​static int[][] dp = new int[501][501];

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​input();

​​​​​​​​for (int len = 1; len <= n; len++) {
​​​​​​​​​​​​for (int s = 1; s <= n - len + 1; s++) {
​​​​​​​​​​​​​​​​int e = s + len - 1;

​​​​​​​​​​​​​​​​if (len == 1) {
​​​​​​​​​​​​​​​​​​​​dp[s][e] = 0;
​​​​​​​​​​​​​​​​} else if (len == 2) {
​​​​​​​​​​​​​​​​​​​​dp[s][e] = arr[s].r * arr[s].c * arr[e].c;
​​​​​​​​​​​​​​​​} else {
​​​​​​​​​​​​​​​​​​​​int m = Integer.MAX_VALUE;
​​​​​​​​​​​​​​​​​​​​for (int k = s; k < e; k++) {
​​​​​​​​​​​​​​​​​​​​​​​​int t = dp[s][k] + dp[k + 1][e] + arr[s].r * arr[k].c * arr[e].c;
​​​​​​​​​​​​​​​​​​​​​​​​if (t < m) {
​​​​​​​​​​​​​​​​​​​​​​​​​​​​m = t;
​​​​​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​dp[s][e] = m;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​System.out.println(dp[1][n]);
​​​​}

​​​​static void input() throws IOException {
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​n = parseInt(br.readLine());
​​​​​​​​for (int i = 1; i <= n; i++) {
​​​​​​​​​​​​StringTokenizer st = new StringTokenizer(br.readLine(), " ");
​​​​​​​​​​​​int r = parseInt(st.nextToken());
​​​​​​​​​​​​int c = parseInt(st.nextToken());
​​​​​​​​​​​​arr[i] = new Matrix(r, c);
​​​​​​​​}
​​​​}
}