[알고리즘] 크래프톤 정글 3주차 / 알고리즘 中 혼자서 못 푼 문제 정리 8(행렬 곱셈 순서)

BOJ 11049 행렬 곱셈 순서

난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골3

사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍(DP)

 

처음 생각한 풀이

드디어 고대하고 걱정했던 다이나믹 프로그래밍을 푸는 주간이 와버렸다...

 

정글에 들어오기 전부터 알고리즘 공부를 계속 하긴 했지만 아무리 해도 DP는 익숙해지지도 않고 감도 안와서 가장 걱정했었는데 걱정했던 대로 겁나 어렵다...

 

사실 솔직히 말하면 2시간 동안 온갖 방법을 생각하면서 점화식을 찾으려 노력했지만 예제 문제조차 맞게 나오는 방법을 떠올리지 못했다.

 

결국 동료의 도움을 받아 CLRS(둔기 알고리즘 책 => 학교 다니면서도 이런 책은 본 적이 없다)에 DP 파트에 이 문제에 관한 부분이 있다는 것을 듣고 읽어보려 했지만 역시나 가독성이 안 좋은 책 답게 글이 눈에 들어오지 않아 연쇄 행렬 곱셈을 구글에 찾아보고 풀었다. 

구글링 이후 풀이

구글링을 통해 점화식을 보고 처음 든 생각은 '이 문제를 12시간 동안 봤어도 절대 떠올리지 못했을 점화식이다.' 였다.

 

점화식으로 바로 가겠다.

먼저 입력받은 행렬의 개수 N을 이용하여 DP행렬을 N * N 로 선언해두자.

 

이때 DP[ i ][ j ]는 i 번째 행렬부터 j 번째 행렬까지 곱했을 때의 최소 곱셈 연산 횟수를 의미한다.

DP[ i ][ i ]는 항상 0으로 초기화해둔다.(행렬이 하나만 있을 때에는 연산이 없으므로)

 

점화식은 다음과 같다.

수식 수정 예정(i <= k <= j - 1 이 맞다)

 

k : i 부터 j - 1까지 순회하며 결합의 위치를 나누어주는 변수이다.

di dk dj = di by dk 행렬과 dk by dj 행렬의 곱셈 연산 횟수 di * dk * dj 를 의미한다.

 

풀어서 설명하자면 i 번째 행렬부터 j 번째 행렬까지 곱했을 때의 최소 곱셈 연산 횟수는 원래 DP값과

i 부터 k 까지의 곱셈 연산 횟수 + k + 1 부터 j 까지의 곱셈 연산 횟수 + d(i-1) * dk * dj 중 최소값이다.

 

이해가 안된다면 코드를 통해 이해를 해도 좋다.

필자도 처음에는 뭔소린가 하고 코드를 보고 이해했다.

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

코드

import sys

N = int(sys.stdin.readline())

matrix = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[99999999999 for _ in range(N)] for _ in range(N)]      # dp[i][j] : i번째 matrix부터 j번째 matrix까지 곱했을 때의 최소 곱셈 연산 횟수

for i in range(N):

    dp[i][i] = 0    # 행렬이 1개면 연산 X

for i in range(N):

    for j in range(0, N - i):

        if j == j + i:      # i = 0인 경우는 행렬 j ~ j 까지의 곱만 보는 것이므로 보지 않음

            continue

        a = j

        b = j + i

        for k in range(a, b):

            dp[a][b] = min(dp[a][b], dp[a][k] + dp[k + 1][b] + matrix[a][0] * matrix[k][1] * matrix[b][1])

            # a번째 ~ b번째 행렬들을 다 곱했을 때 최소 연산 수 구하는 과정

            # a ~ k 연산 수 + k+1 ~ b 연산 수 + 두 연산의 결과로 나온 행렬의 연산 수

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