[백준 11049번] 행렬 곱셈 순서 (python)

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

 

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

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

 

기록

(dp 17일차) 문제 제대로 안 읽어서 순서대로 입력값이 들어온다는 걸 몰랐다..... 덕분에 엄청 헤맸다ㅠ 그리고 최솟값 구하기 위해 1e9로 초기화했다가 그보다 더 큰 수가 나올 수 있다는 걸 알고 2^31로 바꿔줬다.

 

문제에서 나온 예시대로 배열을 채워나가는 과정이다. dp[i][j]에는 i번째 앞의 숫자로 시작해서 j번째 뒤의 숫자로 끝나는 행렬의 연산 횟수가 저장되며, 오른쪽 아래 대각선 방향으로 배열을 채워나간다.

 

다음은 5로 시작해서 2로 끝나는 행렬의 연산횟수를 저장하는 방법이다. 5로 시작해서 2로 끝나는 행렬을 만들 수 있는 모든 방법을 비교하여 최솟값을 찾아야하며, 다음과 같은 경우는 행렬을 만들 수 있는 방법은 5*3*2 한 가지이다.

 

다음은 5로 시작해서 6으로 끝나는 행렬의 연산횟수를 구할 차례이다. 이번에는 5x3보다 (3x2와 2x6)을 먼저 구하는 방법, (5x3과 3x2)를 먼저 구하고 2x6을 하는 방법 두 가지 이기 때문에 값을 비교하여 작은 값을 저장한다.

 

위와 같이 구한 결과, 5x3, 3x2, 2x6 행렬의 최소 연산횟수는 90이 된다.

 

코드

n = int(input())
mat = [tuple(map(int, input().split())) for i in range(n)]

dp = [[0]*n for i in range(n)]
for cnt in range(n-1):
    for i in range(n-1-cnt):
        j = i+cnt+1
        dp[i][j] = 2**31
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + mat[i][0]*mat[k][1]*mat[j][1])
print(dp[0][-1])

1. 변수를 초기화하고 i번째 앞의 숫자로 시작해서 j번째 뒤의 숫자로 끝나는 행렬의 최소 연산 횟수를 저장할 이차원 dp배열을 생성한다.

2. 가장 바깥의 반복문은 dp 배열의 n-1개 대각선을 채우기 위해 설정된다.

3. 두 번째 반복문은 dp 배열의 대각선 한 개를 채우기 위해 반복되며, i와 j가 계속해서 갱신된다. i는 대각선의 행을 나타내며, j는 배열의 열을 나타낸다. 

4. 세 번째 반복문에서는 dp[i][j]의 최소 연산 횟수를 찾는다. k는 i부터 j-1까지의 숫자로, dp[i][j] 행렬을 둘로 나누는 경계선 역할을 하여 모든 조합을 비교해보고 최소 연산 횟수를 찾아 저장한다.

5. dp 배열의 가장 오른쪽 위의 원소를 출력한다.