[DP] 백준 - 행렬 곱셈 순서 11049번

행렬 곱셈 순서 11049번

😘 문제 요약

모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오.

👏 key point

• 예시 : ABCD의 행렬의 최솟값을 구하기 위해서는
  A(BCD)
  (AB)(CD)
  (ABC)D
  ABCD

중 최솟값을 구하면 된다. 이때 BCD 값, ABC값들은 ABCD 최솟값을 구하는 과정과 똑같은 과정을 거쳐 답을 구할 수 있다. 따라서 이 문제는 DP(동적계획법) 방식으로 풀면 시간 복잡도도 줄이고 효율적으로 풀 수 있다.

DP 그래프는 다음과 같이 구상할 수 있다.

따라서 맨 처음에는 모두 0의 값을 가지고 있는 dp 이차원 배열 리스트를 만들고 자기 자신을 곱하는 행렬 또한 0이다. (자기 자신은 곱하지 않으므로)

위의 그래프를 보면 ABCD (dp[0][4]) 를 구하기 위해서는 BCD, AB,CD ,ABC값이 필요하며 ABC값을 구하기 위해서는 AB와 BC값이 반드시 필요하다.

초록 - 주황 - 빨강 순으로 그래프를 채워나가야 한다.

😜 코드

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

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

for i in range(1,n):            # i는 간격에 따른 대각선 줄을 의미한다.  
    for j in range(n-i):        # j는 대각선의 항목들
        x = i + j
        dp[j][x] = 2 ** 32

        for k in range(j,x):   # 나올 수 있는 모든 최솟값을 구한다. 
            dp[j][x] = min(dp[j][x], dp[j][k] + dp[k+1][x] + graph[j][0] * graph[k][1] * graph[x][1])

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