난이도 : 골드 3
유형 : DP
https://www.acmicpc.net/problem/11049
문제 접근
행렬의 곱셈을 할때 필요한 곱셈의 연산의 수의 최솟값을 구하는 문제.
우선 행렬의 곱에 대해 다시 리마인드해보자.
행렬 A와 B를 곱하려면,
A의 열의 수와 B의 행의 수가 같아야 한다.
mk 행렬과 kn의 행렬의 결과는 m*n 행렬이 된다.
이때 예제 1을 봐보면
A행렬 (5,3) B행렬(3,2) C행렬(2,6) 이 있을때
이 세 행렬을 곱하면 결국 AxBxC 행렬 (5,6)이 되는 것은 어떤 순서로 곱하든 동일하다. 그러나 연산횟수는 다를 수 있는데
-
AxB 먼저하고 xC 의 경우
AxB 할 때 연산횟수는 5x3x2 = 30 이 되고 행렬은 (5,2) 가 된다.
여기에 C를 곱하면 연산횟수는 526 = 60이 되고 행렬은 (5,6)이 된다.
총 연산횟수는 30 + 60인 90이 된다. -
BxC 먼저 하고 xA의 경우
BxC 할 때 연산횟수는 3x2x6 = 36 이 되고 행렬은 (3,6) 가 된다.
여기에 A를 곱하면 연산횟수는 536 = 90이 되고 행렬은 (5,6)이 된다.
총 연산횟수는 36 + 90인 126이 된다.
이렇듯 어떤 순서로 곱하는 지에 따라 행렬은 같게 나오지만 연산횟수는 달라진다.
그렇다면 행렬의 개수가 3개 일때의 곱은 이렇게 가짓 수가 2가지가 나오는데
행렬의 개수가 A,B,C,D 이렇게 4개 일때는 가짓수가 몇가지 나올까?
- AB 먼저 곱하는 경우 (AB)CD
- BC 먼저 곱하는 경우 A(BC)D
- CD 먼저 곱하는 경우 AB(CD)
이렇게 먼저 곱하는 경우는 3가지인데 곱해진 행렬을 다시 X로 놓고 보면
XCD, AXD, ABX 이렇게 행렬의 개수가 3개일때의 곱으로 볼 수 있다.
이때 경우의 수는 2가지였으니 행렬의 개수가 4개일때는 3*2 가지가 됨을 알 수 있다.
그렇다면? 행렬의 개수가 5개라면? 4x3x2 개가 될텐고
n개라면? n!개가 됨을 알 수 있다.
문제에서 제시한 n의 범위가 최대 500이였으니 브루트포스로 푼다면 최대 499! 가지가 나와서 이 문제는 완전탐색으로 풀 수 없다.
최적의 결과를 낼때는 최적의 과정이 필요하니 그 과정을 배열에 담는 DP방식을 이용해보자.
dp[i][j] 는 ixj 행렬의 곱에 연산횟수의 최소값이다.
dp점화식은 다음과 같다. i와 j 사이의 중간값 k를 기준으로 적절한 k를 설정하며 최적의 답을 배열에 저장한다.
cost = dp[i][k] + dp[k+1][j] + matrix[i][0] matrix[k][1] matrix[j][1]
matrix[i][0] matrix[k][1] matrix[j][1] 이 부분은
비용 계산식인데 , 행렬의 곱은 행렬이 약분되다시피 지워지면서 결국에 행렬의 크기는 첫번째 인덱스의 행, 가운데 인덱스의 열, 마지막 인덱스의 열을 곱해주어야 한다.
해답 및 풀이
import sys
input = sys.stdin.readline
N = int(input())
matrix = [tuple(map(int,input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
for length in range(2, N+1): #부분 문제의 크기(길이)를 2~N까지 순차적으로 늘리면서 풀기 length가 2면 행렬 두개를 곱, 3이면 세개를 곱, 작은수부터 순차적으로 저장해가며 풀어야 뒤에 큰수에서도 쓸 수가 있기때문
for i in range(N - length + 1):
j = i + length - 1 # 부분 구간의 시작을 i, 끝을 j
dp[i][j] = sys.maxsize
for k in range(i, j): # i~j 사이에 어디에 괄호를 칠지 결정
cost = dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]
# 비용 계산식, 행렬이 약분되다시피 지워지면서 결국에 행렬의 크기는 첫번째 인덱스의 행, 가운데 인덱스의 열, 마지막 인덱스의 열을 곱해주어야 함
dp[i][j] = min(dp[i][j], cost)
print(dp[0][N-1]) 