187. 11049(행렬 곱셈 순서) - 파이썬

본 코드는 pypy3로 제출해야 합니다.

import sys
input = sys.stdin.readline

N = int(input())
rc = [list(map(int, input().split())) for _ in range(N)]

DP = [[0]*N for _ in range(N)]

for i in range(1, N):
    for x in range(N-i):
        y = i + x

        DP[x][y] = 2 ** 32

        for k in range(x, y):
            DP[x][y] = min(DP[x][y], DP[x][k] + DP[k+1][y] +
                           rc[x][0] * rc[k][1] * rc[y][1])


print(DP[0][-1])

문제요약

행렬의 곱셈 연산이 제일 적게 이행하는 최솟값을 구하라.

설명

행렬의 곱셈식은

이다.

따라서 연산 횟수는 x*z*y가 된다.

 

 

이 식을 기억하고 입력 예제를 보자.

다음과 같이 행렬의 크기가 주어지면

1. 5 * 3 * 2 + 5 * 2 * 6 = 30 + 60 = 90 

2. 3 * 2 * 6 + 5 * 3 * 6 = 36 + 90 = 126

으로 1번의 연산이 더 적다.

 

일단 DP 리스트에서 우리는 회색 대각선 기준 윗부분만 사용할 것이다.

계산은 각 색깔별로 진행된다.

DP[0][1] -> DP[1][2] -> DP[2][3] -> DP[3][4] -> DP[0][2] -> ... -> DP[0][4]

로 진행되며 DP[0][4] 가 출력값을 지니게 된다. 

 

for i in range(1, N):
    for x in range(N-i):

 

먼저 i는 회색 대각선 하단 부분은 사용하지 않기 위해서 설정한 것이다.

따라서 x를 N-i만큼만 진행되도록 하였다. (다음 행이 될때마다 사용하는 주소가 줄어든다. 4 -> 3 -> 2 -> 1)

 

        y = i + x

y는 i + x로 설정하면 될것이다.

예를들어 

i가 1번째에서 x가 0 이면 arr[x][y] = arr[0][1] 이고, x가 1이면 arr[x][y] = arr[1][2] 이런식으로 진행된다.

 

        DP[x][y] = 2 ** 32

        for k in range(x, y):
            DP[x][y] = min(DP[x][y], DP[x][k] + DP[k+1][y] +
                           rc[x][0] * rc[k][1] * rc[y][1])

최소 값을 구하기 위해서 초반 셋팅값은 2의 32제곱으로 정해주었다.

연산횟수는 2의 31승 -1 보다 작거나 같기 때문에 최대한의 크기로 설정해 준것이다.

 

이제 본격적인 비교가 들어가는데 k를 x~y범위로 하여 계산을 진행한다.

 

아까 위에서 연산 횟수를 구할 때 식을 보면

[x][0] + ([x][1] 혹은 [y][0]) + [y][1] 인 것을 볼 수 있다.

즉, [x][0] + ?? + [y][1] 이라는 것을 알 수 있고, ??는 x 혹은 y가 들어가게 되어 k를 위와같이 설정해주었다.

 

 

DP[x][k] + DP[k+1][y]는 다음을 표시한것이다

빨간색 (현재)를 구하기 위해 노란색(DP[x][k] + DP[k+1][y]) 부분을 이용한 것이다.

 

 

결국 마지막 부분까지 하면 총 계산이 끝난 거고

x가 0 y가 끝부분을 가리 키는 빨간색 부분이 답이 된다.