11049. 행렬 곱셈 순서 (Python)

11049번: 행렬 곱셈 순서

 

풀이

 2차원 dp를 활용하여 구할 수 있다. 2차원 dp는 다음을 의미한다.

 위의 예제는 dp[2][5]를 구하는 과정 중 하나의 예를 나타낸다. dp[2][5]를 구하기 위해서는 다음과 같은 경우를 모두 탐색해야 한다.

• dp[2][2] + dp[3][5] + 곱셈 연산
• dp[2][3] + dp[4][5] + 곱셈 연산
• dp[2][4] + dp[5][5] + 곱셈 연산

 이 중 최솟값이 dp[2][5]에 기록된다. 

 

 이를 구하는 점화식은 다음과 같다.

    for k in range(2, N): # 시작하는 행렬부터 k만큼 떨어진 행렬까지의 연산의 최솟값을 구한다.
        for i in range(0, N-k): # i는 시작하는 행렬을 말한다.
            dp[i][i+k] = INF
            for j in range(i, i+k): # j는 구간을 나누는 기준이 되는 행렬을 의미한다. 
                dp[i][i+k] = min(dp[i][i+k], dp[i][j] + dp[j+1][i+k] +
                                 matrix[i][0] * matrix[j][1] * matrix[i+k][1])

 

 위의 예제를 통해서 점화식을 이해하면 다음과 같다.

 

 

코드

INF = float('INF')

if __name__ == '__main__':
    N = int(input())
    matrix = []

    for i in range(N):
        matrix.append(list(map(int, input().split())))

    # dp[a][b] : a번째 행렬부터 b번째 행렬까지 필요한 곱셈 연산의 최솟값
    dp = [[0 for _ in range(N)] for _ in range(N)]

    # 한 칸 떨어진 행렬의 곱셈 연산의 최솟값은 그냥 둘을 곱했을 때의 연산 횟수와 같다.
    for i in range(N-1):
        dp[i][i+1] = matrix[i][0] * matrix[i][1] * matrix[i+1][1]

    for k in range(2, N): # 시작하는 행렬부터 k만큼 떨어진 행렬까지의 연산의 최솟값을 구한다.
        for i in range(0, N-k): # i는 시작하는 행렬을 말한다.
            dp[i][i+k] = INF
            for j in range(i, i+k): # j는 구간을 나누는 기준이 되는 행렬을 의미한다. 
                dp[i][i+k] = min(dp[i][i+k], dp[i][j] + dp[j+1][i+k] +
                                 matrix[i][0] * matrix[j][1] * matrix[i+k][1])

    # 마지막에 시작부터 끝까지에 해당하는 dp[0][N-1]을 출력해주면 된다.
    print(dp[0][N-1])