[백준 11049번] 행렬 곱셈 순서 문제 풀이

 

< 문제 >

 

 

< 입출력 >

 

 

 

< 풀이 >

주어진 행렬의 최소 곱셈 연산을 구하는 문제이다.

dp를 이용해서, dp[i][j]에 i+1번째 행렬부터, j+1번째 행렬까지 곱했을 때의 곱셈 연산 횟수의 최솟값을 저장해서 풀었다.

 

 

 

 

< 코드 >

N = int(input())
arr = []
INF = int(1e9)

for _ in range(N):
    r, c = map(int, input().split())
    arr.append((r, c))

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

for i in range(N - 1):
    dp[i][i + 1] = arr[i][0] * arr[i + 1][0] * arr[i + 1][1]

for L in range(2, N):
    i = 0
    j = L

    while j < N:
        dp[i][j] = INF
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i][0] * arr[k][1] * arr[j][1])
        i += 1
        j += 1

print(dp[0][N - 1])