백준) 11049 행렬 곱셈 순서

11049. 행렬 곱셈 순서

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최소값을 구하는 프로그램을 작성하시오.

입력으로 주어진 행렬의 순서를 바꾸면 안된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최소값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다.

예제 입력 

3
5 3
3 2
2 6

예제 출력 

90

1. 접근

행렬 곱셈 연산의 수를 계산하는 방법이 따로 존재할 때, 임의의 행렬들이 주어질 때(순서는 고정), 어떤 행렬들 부터 곱해나가야 연산을 가장 적게하는지 묻는 문제다.

행렬들이 ABCD 로 주어진다면 다음의 곱셈 순서들이 가능하다

1) { { { A * B } * C } * D }

2) { { A * B } * { C * D } }

3) { { A * { B * C } } * D }

 

4) { A * { B * { C * D } } }

5) { A * { { B * C } * D } }

역시나 위의 순서들을 빠르게 만들어 낼 수 있는 패턴을 찾아내는게 포인트다. 

그러면 패턴을 구현해내고, 다이나믹 프로그래밍으로 빠르게 연산 수를 계산할 수 있겠다.

2. 풀이

패턴 : 묶음은 그보다 작은 두 묶음으로 재귀적으로 나눠진다.

2)의 경우 가장 큰 묶음은 { A * B } 와 { C * D } 로 나눠진다. 나머지 경우들은 2번씩 나눠진다.

그러면 DP 배열을 다음과 같이 정의해보자.

DP[X][Y] = 인덱스 x인 행렬부터 y까지 주어졌을 때, 우리가 원하는 정답을 보관한다.

그러면 다음과 같은 재귀함수로 배열을 갱신해 나갈 수 있다.

func(int x, int y) = DP[X][Y]를 계산하는 함수

재귀함수가 탈출하기위한 기저사례는 무엇일까?

간단히 두행렬을 곱하는 경우는 쉽게 연산 수를 계산할 수 있다.

하지만 구현을 더 간단히 하기 위해 x==y 인 경우로 탈출시키자. -> 연산하지 않는다 = return 0

이제 두 묶음으로 나눌 수 있는 경우들을 구현해야 한다.

나누는 기준은 x~y까지 가능하다. 

for (int k = x; k < y; ++k)

mm = min(mm, func(x, k) + func(k + 1, y) + m[x].r * m[k].c * m[y].c);

// m[k].c = m[k+1].r

나눠주고 계산해주는 함수들을 호출한 다음, 최소값을 기록하면 된다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
struct mat {
    int r, c;
};
mat m[501];
 
int dp[501][501];
int n, i;
 
int func(int x, int y) {
    if (x == y)
        return 0;
 
    int& ref = dp[x][y];
    if (ref != -1)
        return ref;
 
    int mm = INT_MAX;
 
    for (int k = x; k < y; ++k)
        mm = min(mm, func(x, k) + func(k + 1, y) + m[x].r * m[k].c * m[y].c);
 
    return ref = mm;
}
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d %d", &m[i].r, &m[i].c);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, n - 1));
    return 0;
}

4. 후기

하나씩 곱해야 하는 줄 알고 삽질좀 했다.