모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오.
중 최솟값을 구하면 된다. 이때 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])