BOJ 11049 행렬 곱셈 순서(C++)

행렬 곱셈 순서 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1012	444	299	44.035%

문제

크기가 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

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include    <cstdio> #include    <limits> #define min(x,y) ((x)<(y)?(x):(y)) #pragma warning (disable:4996)   int M[555][2]; // 0 : r , 0 : c int D[555][555]; int main() {     int N;     scanf("%d", &N);       for (int i = 1; i <= N; ++i)         scanf("%d%d", &M[i][0], &M[i][1]);       for (int i = N; i > 0; --i)     {         for (int j = i + 1; j <= N; ++j)         {             D[i][j] = std::numeric_limits<int>::max();             for (int k = i; k <= j; ++k)                 D[i][j] = min(D[i][j], D[i][k] + D[k+1][j] + (M[i][0] * M[k][1] * M[j][1]) );         }     }       printf("%d", D[1][N]); }

dynamic programming

이전에 풀었던 교차하지 않는 원의 현들의 최대집합 문제와 유사하다. 

이것도 결국 어떻게 보면

D[i][j]가 i번째부터 j번째 행렬까지의 곱 중 가장 적은 연산을 할 경우의 연산수라고 한다면 

이는 i~j사이의 임의의 k를 놓고 i~k까지의 최소연산수 + k+1~j의 최소연산수 + 두 행렬의 연산수 중 가장 적은 연산수가 될 것이다. 

결국 k가 i~j 사이일 때 

D[i][k] + D[k+1][j] + 두 행렬의 연산수를 계산하면 된다. 

이것도 다이나믹 프로그래밍 이므로 작은 것들을 먼저 연산하고, 그것을 큰 문제에 사용해야 하므로 i, j의 for loop 중 i를 N부터 1까지 1씩 줄여가며 사용하였다. 

N이 10일 경우 

D[9][10] => D[8][9] => D[8][10] 순서로 작은 경우부터 차례대로 계산하여 D[8][10]을 구할 때 이미 D[9][10]과 D[8][9]를 구했기 때문에 사용이 가능하다.