[다이나믹 프로그래밍] 백준 11049번 : 행렬 곱셈 순서 / 골드 3

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

11049번: 행렬 곱셈 순서

n = int(input())
info = []
for _ in range(n):
    info.append(list(map(int, input().split())))

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

for i in range(2, n+1):  # i는 글자 수
    for j in range(n-i+1):  # j는 시작 인덱스
        dp[i][j] = 2**32
        for k in range(1, i):
            val = dp[i-k][j] + dp[k][j+i-k] + info[j][0]*info[j+i-k][0]*info[j+i-1][1]
            dp[i][j] = min(dp[i][j], val)
print(dp[-1][0])

예전에 한번 시도했다가 못풀고 이번에 드디어 풀었다.

 

ABCD가 있을 때 최솟값을 구하는 방법은

(ABC)D 

(AB)(CD)

A(BCD)

중 작은 값을 찾아야 되고,

이때 (ABC)D를 찾을 때 (ABC) 부분은 다시

(AB)C

A(BC)

중 작은 값을 비교해가며 찾아야 한다.

 

이는 dp를 이용하여 빠르게 계산할 수 있다.

나같은 경우에 dp 테이블의 세로 축을 글자 수, 가로축을 시작 위치(인덱스)로 잡았는데 

그러다보니까 인덱스가 위의 코드에서 보는 바와 같이 굉장히 복잡하고 어려워졌다.

 

다른 정답 코드를 참고하니 세로, 가로축을 각각 시작 위치, 종료 위치로 잡으니 훨씬 인덱싱이 간결해졌다.

이 점을 깊이 새기고 다음부턴 인덱싱에 좀 더 신경을 써야겠따.