[백준/c++] 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)

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

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 2^31-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 2^31-1보다 작거나 같다.

사용 알고리즘

• dp(점화식과 메모이제이션을 사용)

규칙

• 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 "연산 횟수"의 "최솟값"을 구합니다.
• 정답과 연산횟수는 2^31-1(2,147,483,647) 보다 작거나 같으므로, -2,147,483,648 ~ 2,147,438,647의 범위를 가지는 int형을 사용합니다.

풀이

11066번 - 파일 합치기 문제와 마찬가지로, 구간을 나누어 더해줍니다.

d[i][j]는 d[i]~d[j]까지의 행렬곱인데, 파일 합치기 문제와 마찬가지로 구간을 d[i]~d[k], d[k+1]~d[j]로 나누어서 생각합니다.

d[i]~d[j]의 행렬곱 연산횟수는 아래 3부분의 합으로 표현할 수 있습니다.

1. d[i][k]의 행렬곱

2. d[k+1][j]의 행렬곱

3. mat[k]와 mat[k+1]의 행렬곱(mat : 입력값을 초기화 한 배열)

따라서, 점화식은

d[i][j] = d[i][k] + d[k+1][j] + (mat[k]와 mat[k+1]의 행렬곱) 입니다.

코드(시간 복잡도 N^3)