[백준 11049번] 파이썬 - 행렬 곱셈 순서

http://www.acmicpc.net/problem/11049

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)
• 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

 

# 접근방법

• DP를 이용하여 행렬을 곱하는데 필요한 곱셈의 최소 횟수를 담아준다. - 연쇄 행렬 곱셈 이용
  • dp[i][j] 는 matrix[i]에서 matrix[j] 까지 행렬을 곱하는데 필요한 곱셈의 최소 횟수를 뜻한다.
  • 즉 i번째 행렬과 j번째 행렬을 곱할 때, 연산이 최소가 되는 횟수

min(ABCD) = min(
dp[ABCD],
dp[A] + dp[BCD] + A[0] A[1] D[1],
dp[AB] + dp[CD] + A[0] B[1] D[1],
dp[ABC] + dp[D] + A[0] C[1] D[1]
) =   min(
dp[0][4],
dp[0][0] + dp[0][3] + A[0] A[1] D[1],
dp[0][1] + dp[1][3] + A[0] B[1] D[1],
dp[0][2] + dp[2][3] + A[0] C[1] D[1],
)

•  i부터 j까지 곱하는 경우를 생각할 때, 그 사이에 먼저 곱하는 행렬이 존재할 수도, 그렇지 않을 수도 있다.
• 존재하지 않는다면 k는 항상 i과 같거나, j와 같아야 한다.
• 그런데, 존재한다면 어디서 존재하는 지를 알아야 하는데, 이는 불가능하다.
• 따라서 먼저 곱해지는 행렬의 위치를 또다른 변수 k로 놓는다면, 항상 i와 j의 곱하는 연산의 최소값은
  • i와 k까지의 연산의 최소값 + k + 1과 j까지의 연산의 최소값이라 할 수 있다.
• 따라서 D[0][3]은 k가 0,1,2가 될 수 있으며, 위의 표처럼 D[0][2]를 채우는 논리만 적용한다면, k가 0,2일때만 D[0][3]의 경우를 구하는 것이므로 k의 모든 경우에 대해 D[0][3]의 값을 갱신할 수 없다.
• 이 경우 k가 1인 경우가 최소이며 D[0][3]은 231이 아니라 184이다.

 

pypy 제출

N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
# 곱셈의 최소 횟수 행렬
dp = [[0]*N for _ in range(N)]

for diagonal in range(1, N):  # dp[i][i]는 자기 자신의 행렬이기 때문에 값이 0
    for i in range(0, N-diagonal):  # 대각선의 우측 한 칸씩 이동
        j = i + diagonal  # 현재 대각선에서 몇 번째 원소인지
        # 차이가 1밖에 나지 않는 칸
        if diagonal == 1:
            dp[i][j] = matrix[i][0] * matrix[j][0] * matrix[j][1]
            continue

        dp[i][j] = float('inf')
        # 각 부분행렬의 곱셈 횟수 + 두 행렬의 곱셈 횟수
        for k in range(i, j):  # k값으로 최적분할 찾기
            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][N-1])

 

다른 분 코드 - python 제출

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]
arr = [a for a, _ in arr] + [arr[-1][1]]
dp = [[0] * n for _ in range(n)]

for step in range(1,n):
    for loc in range(n-step):
        end = loc + step
        mul = arr[loc] * arr[end+1]
        minimum =  min(yk + xk + sz * mul for yk, xk, sz in zip(dp[loc][loc:end], dp[end][loc+1:end+1], arr[loc+1:end+1]))
        dp[loc][end] = dp[end][loc] = minimum

print(dp[0][-1])