백준 11049번 행렬 곱셈 순서 - 스위프트(Swift) 풀이

1. 두 부분으로 잘라 앞쪽 행렬끼리 곱하고, 뒤쪽 행렬끼리 곱한 뒤, (앞쪽 행렬들을 모두 곱한 결과 행렬)과 (뒤쪽 행렬들을 모두 곱한 결과 행렬)을 곱하는 방식을 사용한다.
2. dp(lo, hi) = lo부터 hi번째 행렬을 전부 곱하는 데 필요한 연산 횟수의 최솟값이라고 하면
3. dp(lo, hi) = i=lo~hi-1일 때 min( dp(lo, i) + dp(i+1, hi) + matrix[lo].row * matrix[i].col * matrix[hi].col )

---

1. 두 부분으로 잘라 앞쪽 행렬끼리 곱하고, 뒤쪽 행렬끼리 곱한 뒤, (앞쪽 행렬들을 모두 곱한 결과 행렬)과 (뒤쪽 행렬들을 모두 곱한 결과 행렬)을 곱하는 방식을 사용한다.

 브루트포스로는 시간 내에 통과가 불가능하다. DP를 사용할 것이다. 분할 정복과 비슷하게 위와 같은 방식으로 곱셈을 해나간다.

 

2. dp(lo, hi) = lo부터 hi번째 행렬을 전부 곱하는 데 필요한 연산 횟수의 최솟값이라고 하면

 부분곱을 나타내기 위해 dp(lo, hi)를 정의한다.

 

3. dp(lo, hi) = i=lo~hi-1일 때 min( dp(lo, i) + dp(i+1, hi) + matrix[lo].row * matrix[i].col * matrix[hi].col )

 N x K 행렬과 K x M 행렬을 곱한 결과는 N x M 행렬이다. 따라서 앞쪽 행렬(lo~i)끼리 곱한 결과는 (matirx[low].row x matrix[i].col)이 되고, 뒤쪽 행렬(i+1~hi)끼리 곱한 결과는 (matrix[i+1].row x matrix[hi].col)이 된다. 이때 곱셈이 가능한 경우만 주어지므로 당연히 matrix[i].col == matrix[i+1].row이다. 따라서 앞뒤 결과 행렬을 곱하는데 드는 연산 횟수는 (matrix[lo].row * matrix[i].col * matrix[hi].col)으로 나타낼 수 있다.

 이것이 끝이 아니라 앞뒤 결과 행렬을 각각 얻기까지의 연산 횟수도 더해주어야 한다. 각각 재귀적으로 dp(lo, i), dp(i+1, hi)로 구할 수 있다. 따라서 i를 기준으로 반으로 갈라 곱셈을 했을 때의 총 연산 횟수는 dp(lo, i) + dp(i+1, hi) + matrix[lo].row * matrix[i].col * matrix[hi].col이다.

 i가 될 수 있는 모든 경우(두 부분으로 자르는 모든 경우)를 고려하여 그중 연산 횟수의 최솟값을 구하면 된다.

 

---

import Foundation

typealias Pair = (row: Int, col: Int)

var N = 0
var matrix = [Pair]()
var cache = Array(repeating: Array(repeating: -1, count: 501), count: 501)

// dp(lo, hi) = lo부터 hi번째 행렬을 전부 곱하는 데 필요한 연산 횟수의 최솟값
func dp(lo: Int, hi: Int) -> Int {
    if lo == hi { return 0 }
    
    var ret = cache[lo][hi]
    if ret != -1 { return ret }
    
    for i in lo..<hi {  // 반으로 잘라 (왼쪽 결과 * 오른쪽 결과)
        let cost = dp(lo: lo, hi: i) + dp(lo: i+1, hi: hi) + matrix[lo].row * matrix[i].col * matrix[hi].col
        ret = ret == -1 ? cost : min(ret, cost)
    }
    
    cache[lo][hi] = ret
    
    return ret
}

func solution() {
    N = Int(readLine()!)!
    
    for _ in 0..<N {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        matrix.append((row: input[0], col: input[1]))
    }
    
    print(dp(lo: 0, hi: N-1))
}

solution()