[백준] 28. 행렬 곱셈 순서 11049 해설

행렬 곱셈 순서

11049번: 행렬 곱셈 순서

문제

 

2차원 배열을 이용한 DP문제라는 것을 알아도 아이디어를 찾고 구현하는 데까지 꽤 까다로웠던 문제입니다.

풀이

최소한의 연산 횟수가 나올 수 있도록 행렬의 곱셈 순서를 결정해 주면 되는 문제입니다.

다만 행렬이기 때문에 행렬의 앞 뒤 순서는 지켜줘야 됩니다.

ex) 행렬 A, B, C 가 주어졌을 때
- A x B x C    가능
- A x (B x C)  가능
- A x C x B    불가능

 

처음에는 뭔가 수학적 이론을 이용한 문제인가 싶었지만 행렬이라는 카테고리 자체의 난이도가 있기 때문에 가장 간단한 완전탐색으로 접근해 보았습니다.

 

행렬 A, B, C, D, E가 있을 때 계산 결과에 따라 나올 수 있는 경우는 다음과 같습니다.

행렬 1개인 경우	A	B	C	D	E
행렬 2개인 경우	AB	BC	CD	DE
행렬 3개인 경우	ABC	BCD	CDE
행렬 4개인 경우	ABCD	BCDE
행렬 5개인 경우	ABCDE

 

뭔가 표로 만들고 보니 2차원 배열의 DP를 이용하여 풀 수 있을 거 같습니다.

 

위의 표만으로 간단하게 끝나면 좋지만

행렬 3개인 ABC의 경우를 보면 ABC가 될 수 있는 경우가 또 여러 가지로 나뉠 수가 있습니다.

A-BC, AB-C

그렇다면 추가적으로 ABC의 값에는 A-BC와 AB-C의 연산 값 중에 최소값을 넣어주면 됩니다.

ABC = min(A-BC, AB-C)

 

좀 더 복잡한 경우인 4번의 ABCDE을 보면 아래와 같습니다.

4번 : A-BCDE, ABCD-D, AB-CDE, ABC-DE

결국 ABCDE가 되는 경우는 행렬 사이사이에 -를 넣어줌으로써 알 수 있습니다.

그로 인해 자연스럽게 (행렬의 개수-1)의 경우만 비교해 주면 된다는 것도 알 수 있습니다.

 

참고로 AB-CD-E 같은 경우도 있다고 생각할 수 있지만 AB-CD는 ABCD, CD-E는 CDE로 이미 이전에 최소값을 구한 상태이기 때문에 결국 ABCD-E와 AB-CDE와 동일해집니다.

 

 

이제 이를 이용하여 코드로 구현해 주면 됩니다.

저는 위에 있는 표 형태 그대로 2차원 배열을 만들어줘서 구현해 주었지만 이럴 경우 점화식이 굉장히 괴랄해지는 문제가 있기 때문에 좀 더 간단한 다른 풀이를 가져왔습니다.

 

 

아래와 같이 행은 시작 행렬, 열은 끝 행렬인 2차원 배열 만들어 줍니다.

값에는 해당 행렬의 최소 연산값을 넣어줍니다.

 

이제 행렬의 개수가 1일 때부터 차례대로 값을 구해주면 됩니다.

행렬 1개인 경우

 

행렬의 개수가 2개인 경우입니다. 

AB를 보면 dp[A] + dp[B] + A와 B의 연산 값이 들어갑니다. (숫자는 임의로 넣어주었습니다)

행렬 2개인 경우

 

행렬의 개수가 3개인 경우입니다.

ABC를 구하기 위해 아래와 같은 식이 만들어집니다.

min (dp[A] + dp[BC] + A와 BC의 연산값, dp[AB] + dp[C] + AB와 C의 연산값)

행렬 3개인 경우

 

마지막 행렬의 개수가 5개인 경우입니다.

ABCDE를 구하기 위해서는 아래의 표에 색이 동일한 경우끼리 연산을 하여 다른 색들과 비교해 주면 됩니다.

행렬 5개인 경우

 

이제 위와 같이 계산이 이루어지도록 코드로 구현해 주면 됩니다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    data class Matrix(val r: Int, val c: Int)

    val N = input()

    val dp = Array(N) {IntArray(N)}
    val arr = Array(N) {Matrix(input(), input())}

    for (len in 1 until N) {  // 행렬의 개수에 대해
        for (start in 0 until N-len) {  // 시작 지점 = 행
            val end = start + len       // 끝 지점 = 열
            dp[start][end] = Int.MAX_VALUE

            // 하위 행렬 연산 비교 과정
            for (mid in start until start+len) { 
                
                val cost = dp[start][mid] + dp[mid+1][end] + arr[start].r * arr[mid].c * arr[end].c
                if (dp[start][end] > cost)
                    dp[start][end] = cost
            }
        }
    }
    print(dp[0][N-1])
}