[백준/11049/파이썬] 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

Problem

• 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

조건

• 첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.
• 둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)
• 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

SOL

연쇄행렬 곱셈에서, 최적의 행렬 곱셈의 순서를 알아내는것이 아니라, 최소값을 구하는 문제이다.

하지만, 최적의 행렬 곱셈의 순서를 알아내는 과정에 들어있는 것이므로, CMM 문제라고 생각할 수있음.

Upper Diagnal 방식으로 DP table을 채우는 방식이 익숙하지 않지만, 이 방법을 잘 활용할 수 있게 된다면, 더 많은 문제를 풀 수 있게될거 같다. 

#chained matrix Mul

N = int(input())
matrix=[list(map(int,input().split())) for _ in range(N)]
DP=[[0]*(N) for _ in range(N)]

for diagnal in range(1,N):
    for i in range(0,N-diagnal):
        j=i+diagnal
        if diagnal==1:
            DP[i][j] = matrix[i][0]*matrix[j][0]*matrix[j][1]
            continue
        DP[i][j] = float('inf')
        
        for k in range(i,j):
            DP[i][j] = min(DP[i][j],DP[i][k]+DP[k+1][j]+(matrix[i][0]*matrix[k][1]*matrix[j][1]))

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

#Upper diagnal 방식

N = int(input())

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

cnt=0
for diagnal in range(1,N):
    for i in range(0,N-diagnal):
        j=i+diagnal
        cnt +=1
        DP[i][j] = cnt

for d in DP:
    print(d)
print(DP)