[백준] (11049) 행렬 곱셈 순서 [Python]

문제 링크

https://www.acmicpc.net/problem/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보다 작거나 같다.

예제 입력	예제 출력
3 5 3 3 2 2 6	90

강의 영상

문제가 어렵고 점화식이 난해하기 때문에, 부분의 문제가 해결되었다고 가정하고 점화식을 떠올려 보는 것도 점화식을 세울 수 있는 좋은 방법 중 하나이다.

문제 분석하기

행렬의 개수 N이 주어지고, 1~N개를 모두 곱했을 때 최소 연산 횟수를 구해야 한다. 만약 N개 이외의 부분 영역, 예를 들어 1~N-1, 2~N, 3~N-2 등 N을 제외한 모든 부분 구역을 하나의 행렬로 만드는 데 필요한 최소 연산 횟수를 알고 있다고 가정해보자. 이러한 가정을 바탕으로 1~N 구역의 최소 연산 횟수는 어떻게 구할 수 있을까? 먼저 점화식을 정의해보자.

D[i][j] : i ~ j 구간의 행렬을 합치는 데 필요한 최소 연산 횟수

D[i][j-1], D[j][j]의 값을 안다고 가정했으므로, 이때 하나의 행렬로 합치는 데 드는 횟수는 다음과 같다.

D[i][j-1] + D[j][j] + a # 1개의 행렬도 합치는 데 드는 횟수

여기서 a는 두 행렬을 합치는 데 드는 값으로, 2×3과 3×6 행렬이 있다면 2*3*6 = 36이다. 이 때는 i번째 행렬의 row 개수, j번째 행렬의 column 개수를 곱하면 된다.

이 아이디어를 바탕으로 생각하면 위와 같이 D[1][N]의 값을 찺을 찾는 식을 구할 수 있다.

손으로 풀어 보기

• 행렬 구간에 행렬이 1개일 때 0을 return한다.
• 행렬 구간에 행렬이 2개일 때 앞 행렬의 row값 * 뒤 행렬의 row 값 * 뒤 행렬의 column 값을 return한다.
• 행렬 구간에 행렬이 3개 이상일 때는 다음 조건식의 결과값을 return한다.

# s: 시작 인덱스, e: 종료 인덱스
for (i를 시작 행렬부터 종료 행렬까지 반복하기):
	a = s 행렬의 row * i+1 행렬의 row * e 행렬의 column
	result = min(result, D[s][i] + D[i+1][e] + a)

Top-Down식의 접근법

🤖 "행렬 곱셈 순서 문제의 점화식이 왜 그렇게 되는지 자세히 설명해 드리겠습니다."
문제의 핵심 이해

• 행렬 곱셈은 결합 법칙이 성립합니다. 즉, (A * B) * C = A * (B * C)입니다.
• 하지만 곱셈 순서에 따라 총 연산 횟수가 달라집니다.
• 주어진 행렬들의 순서를 변경할 수 없으므로, 모든 가능한 곱셈 순서를 고려하여 최소 연산 횟수를 찾아야 합니다.

점화식의 구성 요소
점화식 dp[i][j] = min(dp[i][k] + dp[k + 1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1])은 다음과 같은 세 부분으로 구성됩니다.

1. dp[i][k]:
   • i번째 행렬부터 k번째 행렬까지의 곱셈 연산의 최소 횟수입니다.
   • 즉, 부분 문제 i부터 k까지의 최적 해입니다.
2. dp[k + 1][j]:
   • k+1번째 행렬부터 j번째 행렬까지의 곱셈 연산의 최소 횟수입니다.
   • 역시, 부분 문제 k+1부터 j까지의 최적 해입니다.
3. matrix[i][0] * matrix[k][1] * matrix[j][1]:
   • i부터 k까지의 곱셈 결과 행렬과 k+1부터 j까지의 곱셈 결과 행렬을 최종적으로 곱하는 연산 횟수입니다.
   • 행렬의 크기를 표현할때 r*c 로 표현을 하게 되는데, i부터 k까지 곱한 결과의 행렬의 크기는 i행렬의 r값 k행렬의 c값이 되고, k+1부터 j까지 곱한 결과의 행렬의 크기는 k+1행렬의 r값 j행렬의 c값이 됩니다.
   • 따라서 두 행렬을 곱하는 연산의 횟수는 i행렬의 r값 * k행렬의 c값 * j행렬의 c값이 됩니다.

점화식의 논리

• i번째 행렬부터 j번째 행렬까지의 곱셈을 계산할 때, k를 기준으로 두 부분으로 나눌 수 있습니다.
• 즉, (i부터 k까지의 곱셈) * (k+1부터 j까지의 곱셈)으로 나눌 수 있습니다.
• 이때, k는 i부터 j-1까지 모든 가능한 분할 지점을 의미합니다.
• 각 분할 지점 k에 대해 위에서 설명한 세 부분의 합을 계산하고, 그중 최소값을 dp[i][j]에 저장합니다. 이러한 방식으로 모든 가능한 분할을 시도하고 최소값을 저장함으로서 최소의 연산값을 구할 수 있습니다.

코드

n = int(input())
arr = list()
for _ in range(n):
    r, c = map(int, input().split())
    arr.append((r,c))
dp = [[-1] * (n+1) for _ in range(n+1)]

def calc(s, e):
    result = float("inf")
    if dp[s][e] != -1: # 이미 계산한 구간일 때
        return dp[s][e]
    if s == e: # 1개 행렬일 때
        return 0
    if s+1 == e: # 2개 행렬일 때
        return arr[s-1][0] * arr[s-1][1] * arr[e-1][1]
    for i in range(s, e): # 3개 이상 행렬일 때
        a = arr[s-1][0] * arr[i-1][1] * arr[e-1][1]
        result = min(result, calc(s, i) + calc(i+1, e) + a) # 앞뒤 구간의 행렬을 합치기 위한 연산 횟수
    dp[s][e] = result
    return dp[s][e]

print(calc(1, n))

 점화식 세우는 게 너무 어렵다...