11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
문제
크기가 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보다 작거나 같다.
코드
import sys
n = int(input())
matrix = []
for _ in range(n):
r, c = map(int, input().split())
matrix.append([r, c])
# i번째부터 j번째까지 최소 연산 수 저장하는 배열
dp = [[sys.maxsize for _ in range(n)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i, n):
if i == j:
dp[i][j] = 0
continue
for k in range(j-i):
dp[i][j] = min(dp[i][j], dp[i][i+k] + dp[i+k+1][j] + matrix[i][0] * matrix[i+k][1] * matrix[j][1])
print(dp[0][n-1])
2차원 배열 dp에는 i번째 행렬부터 j번째 행렬까지 곱하는데 필요한 최소 연산의 수를 저장할 것이다. 그러면 나중에 최종적으로 dp[0][n-1]의 값을 구하면 모든 행렬을 곱하는데 필요한 최소 연산의 수를 구할 수 있다.
그러기 위해 dp 행렬의 값을 오른쪽 아래에서부터 구해나가볼 것이다. 행렬의 순서는 바뀔 수 없다는 조건이 있으므로 우리는 dp 배열을 왼쪽 위에서 오른쪽 아래로 대각선으로 잘랐을 때 윗부분의 값들만 구해주면 된다.
i번째 행렬부터 j번째 행렬을 곱하는 방법은
- i * (i+1 ~ j)
- (i ~ i+1) * (i+2 ~ j)
- ...
- (i~j-1) * j
이렇게 있을 것이다. 이 때 곱하는데 필요한 연산의 수는 곱하려는 두 행렬의 dp 배열에 저장된 연산 수의 합에 두 행렬을 곱하는데 필요한 곱셈 연산의 수를 더한 값이다. 이해하기 편하게 수식으로 표현하면 다음과 같다.
i ~ k번째 행렬과 (k+1) ~ j번째 행렬을 곱한다고 할 때, 다음의 식으로 필요한 연산의 수를 구할 수 있다.
dp[i][i+k] + dp[i+k+1][j] + matrix[i][0] * matrix[i+k][1] * matrix[j][1]
이 식을 이용하여 dp[i][j]의 값을 배열의 오른쪽 아래에서부터 위로 올라가며 구하여 dp[0][n-1]의 값을 구하면 답이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] Summer/Winter Coding(~2018) 스티커 모으기(2) (0) | 2022.10.12 |
---|---|
[Python/파이썬] 프로그래머스 정수 삼각형 (0) | 2022.10.10 |
[Python/파이썬] 백준 7579번 앱 (0) | 2022.09.29 |
[Python/파이썬] 백준 11066번 파일 합치기 (1) | 2022.09.24 |
[Python/파이썬] 백준 2342번 Dance Dance Revolution (0) | 2022.09.09 |