[백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서

[백준_11049] 다이나믹 프로그래밍(DP), 행렬 곱셈 순서

 

행렬 곱셈 순서에 따라 곱셈의 횟수가 달라진다. 행렬이 주어졌을 때 다이나믹 프로그래밍(DP)를 이용하여 곱셈 횟수의 최솟값을 구하는 문제이다. 뭔가 어려운 포인트들이 많아 한 번 정리해두면 좋은 문제이다.

 

 

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

11049번: 행렬 곱셈 순서

 

문제 풀이

 

생각 포인트

 

이 문제에서 중요한 포인트는 3가지 정도 있다.

1. i 번 째 행렬의 행은 i-1 번 째 행렬의 열과 같다는 점
2. diagonal 방향 출력을 위한 반복문 만들기
3. 점화식 세우기

 

• 1번 사실을 유의하여 행렬 저장 리스트를 만들면 된다. 0번에는 1 번 째 행렬의 행을, 1~N 번 째까지는 1~N 번 째 행렬의 열을 넣어준다.  이 문제의 경우 d = [5, 3, 2, 6] 이다.

• 2번 diagonal 방향 출력을 위한 반복문은 직관적이지 않아서 내가 만들었던 순서를 통해 그냥 그때 그때 만들어내는 게 나은 것 같다. diagonal 1은 0으로 채우고 diagonal 2 부터 시작하면 된다. 하기와 같이 천천히 생각해보자. 이 문제보다 행렬의 수가 하나 더 많은 ABCDE를 예로 만들어보자.

 

# i와 j가 1씩 차이나게 출력
N = 4
for i in range(1, N+1):
    j =  i + 1
    print(i,j)
# 1 2
# 2 3
# 3 4
# 4 5

# i가 다시 1부터 반복하기 위해 반복문 추가
N = 4
for r in range(1, N+1):
    for i in range(1, N+1):
        j = i + 1
        print(i,j)
# 1 2
# 2 3
# 3 4
# 4 5
# 위가 총 4번 출력

# r이 증가할수록 i가 감소해야 한다
N = 4
for r in range(1, N+1):
    for i in range(1, N+1-r):
        j = i + 1
        print(i,j)

# 1 2
# 2 3
# 3 4
# 1 2
# 2 3
# 1 2

# i가 증가할 때 j의 값을 증가시킨다.
N = 4
for r in range(1, N+1):
    for i in range(1, N+1-r):
        j = i + r
        print(i,j)

# 1 2
# 2 3
# 3 4
# 1 3
# 2 4
# 1 4

 

• 3번 점화식을 세우는 것이 가장 어렵다. k를 도입하여 ABCD의 곱셈을 생각해보자

행렬 리스트를 d로, memoization을 위한 리스트를 DP[i][j]로 정의할때,

 

k = 1 : (A) (BCD)

k = 2 : (AB) (CD)

k = 3 : (ABC) (D)

 

이렇게 나눠 곱셈한 후 이 중 곱셈 횟수의 최솟값을 DP값으로 저장하면 된다.

 

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + d[i-1] * d[k] * d[j]

 

코드

코드

 

import sys
input = sys.stdin.readline
d = [] # 행렬들 저장
N = int(input().strip())
# 행렬들 저장
for i in range(N):
    x,y  = map(int, input().split())
    if i == 0:
        d.append(x) # 첫 행렬 원소만 행과 열 다 입력
    d.append(y) # 이후 열만 입력

dp_m = [[0]*(N+1) for _ in range(N+1)]
# 점화식을 먼저 세우고 변수를 넣어주는 것이 좋음
for r in range(1,N+1): # x축 다 움직인 후, y축 움직이기 위헤 r 도입
    for i in range(1,N-r+1): # x축
        j = i + r # y축
        dp_m[i][j] = 2 ** 31
        for k in range(i, j): # k는 행렬 곱하는(자르는) 위치
            dp_m[i][j] = min(dp_m[i][j], dp_m[i][k] + dp_m[k+1][j] + d[i-1]*d[k]*d[j]) # 점화식
            print(i,j,k)
print(dp_m[1][N])