백준 11049 행렬 곱셈 순서

출처: www.acmicpc.net/problem/11049

분류: DP

---

접근방식

전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다.

11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 

 

핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데,

X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다.

 

문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면,

(5x3) - 0
(3x2) - 1
(2x6) - 2

0 ~ 1 까지의 최소값은 dp[0][1],
0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 

0 ~ 2 까지의 최솟값은

( [0][1] 을 먼저 연산한 값 + 그 결과와 [2]를 연산한 값 )  vs ( [1][2] 를 먼저 연산한 값 + 그 결과와 [0]를 연산한 값 )

중에 최소를 찾는 것입니다.

시작 ~ 끝 사이의 거리를 d라고 할 때 d를 1부터 차례차례 구해나가면 dp를 완성시킬 수 있습니다.

 

추가적으로 이 문제에서 x~k, k~y 까지의 행렬의 곱을 생각해보면

X(n x m) x ( ) x ........ x K(n x m) x ...... x Y(n x m)

x~k 까지 곱하고 나면 k의 열이 결과의 열이 되기 때문에

x[0] * k[1] * y[1] 로 구해줄 수 있습니다. 

 

 

해결방법

typealias Metrix = (n: Int, m: Int)

func multiple(_ a: Metrix, _ b: Metrix) -> (Int, Metrix) {
    guard a.m == b.n else { fatalError("Invalid Metrix, \(a), \(b)") }
    return (a.n * a.m * b.m, Metrix(a.n, b.m))
}

let N = Int(readLine()!)!
var metrices = [Metrix]()
var dp = [[Int]](repeating: [Int](repeating: 0, count: N), count: N)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    metrices.append((input[0], input[1]))
}

for d in 1..<N {
    for start in 0..<N-d {
        let end = start + d
        var result = Int.max
        for mid in start..<end {
            result = min(result, dp[start][mid] + dp[mid+1][end] + metrices[start].n * metrices[mid].m * metrices[end].m)
        }
        dp[start][end] = result
    }
}

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

 

배운점

파일 합치기가 너무어려웠어서 몇일 쉬고 다시 풀어서 이해하고 이 문제까지도 겨우겨우 혼자 힘으로 풀었다.

행렬 부분의 곱을 생각하지 못해서 처음에 매우 비효율적으로 풀긴 했었으나!