문제
크기가 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 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.
예제 입력 1
3
5 3
3 2
2 6
예제 출력 1
90
나의 풀이
- 이 문제는 완전탐색으로 구현하면 시간초과가 발생하는 문제이다. 따라서 중복되는 부분을 메모이제이션 기법을 활용해 저장하고 활용해 시간복잡도를 줄이는 DP 알고리즘을 떠올려야 한다. 우선, 이 문제는 최적 부분 구조와 중복 부분 문제를 만족하기에 DP 알고리즘에 적합하다. 행렬 A, B, C, D의 최소 곱 회수를 구하는 예시를 생각해보자. ABCD를 (ABC)D로 분할해 계산할 때 (ABC)의 행렬 곱 회수가 최소여야 ABCD 최소 곱 회수를 구할 수 있을 것이다. 따라서 이 문제는 최적 부분 구조를 만족한다고 볼 수 있다. 또한 ABCD를 계산할 때 ((AB)C)D로 계산하든 (AB)(CD)로 계산하든 AB가 반복된다. 따라서 이 문제는 중복되는 행렬 곱 연산이 반복되는 중복 부분 문제이다.
- 중복되는 부분을 저장하는 메모이제이션 기법을 사용하기 위해 이 문제에서는 2차원 배열을 생성하기로 한다. 예제 입력 1을 예시로 들어보면 첫번째로는 왼쪽과 같은 배열을 만들 수 있을 것이다. 순서대로 곱셈을 진행해야 하기에 start는 항상 end보다 작아야 연산하는 의미가 있으므로 2차원 배열의 왼쪽 삼각형은 업데이트하지 않는다. 이 문제에서 DP를 구현할 때 가장 주의해야 하는 부분은 연산에 사용하는 행렬 개수(length)가 작은 연산부터 실행되도록 구현해야 한다는 것이다. 만약에 그렇지 않고 0번째 행렬부터 2번째 행렬까지의 연산을 먼저 수행하고 1번째 행렬부터 2번째 행렬까지의 연산을 수행하게 된다면 최적해를 구할 수 없을 것이다. (곰곰히 생각해보면 당연하지만 생각보다 코드 구현 단계에서 실수하기 쉬운 것 같다.)
- 앞에서 DP 테이블을 초기화하는 방법에 대해 서술했으니 이제 DP 테이블을 업데이트하는 점화식을 생각해보자. 예제 입력 1의 경우는 행렬이 3개밖에 없어 이해가 어려우므로 행렬 A, B, C, D 4개가 주어진 경우를 기반으로 설명하겠다. ABCD 행렬 곱 회수의 최소해를 구하려면 어떤 점화식이 필요할까? 이 문제는 최적 부분 구조를 만족하므로 (ABC)D 또는 (AB)(CD) 또는 A(BCD)를 비교해보면 될 것이다. 즉 두개의 부분 구조로 행렬을 나눌 수 있는 모든 경우에 대한 최소해를 검사해 DP 테이블을 업데이트하게 되는 것이다. (예제 입력 1만을 가지고 생각하다보면 앞, 뒤의 행렬만을 분리해 계산해도 정답이 나오기 때문에 점화식을 잘못 세울 수도 있다.) 따라서 최종적으로 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+matrix[i][0]matrix[k][1]matrix[j][1]) 를 점화식으로 세울 수 있다. (k는 행렬식을 두개의 부분 구조로 나누는 지점을 가리킨다.)
- DP에 익숙해졌다고 생각했는데 아니었음을 다시 한 번 깨달았고 DP 유형의 무궁무진함을 체감할 수 있는 문제였다. Bottom Up DP 알고리즘을 구현할 때 점화식이 작은 부분부터 실행되도록 항상 주의해야 할 것 같다.
import sys
input = sys.stdin.readline
N = int(input())
dp = [[0 for _ in range(N)] for _ in range(N)]
matrix = [list(map(int,input().split())) for _ in range(N)]
for length in range(2,N+1):
for i in range(N-length+1):
j = i+length-1
dp[i][j] = float('inf')
for k in range(i,j):
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+matrix[i][0]*matrix[k][1]*matrix[j][1])
print(dp[0][-1])
SAY CHEESE