BOJ-11049 행렬 곱셈 순서 Swift

문제

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

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

내가 푼 풀이

접근방법: DP

이 문제는 이전에 풀었던 파일합치기 문제와 유사하다

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

 

연산에 순서에 따라 총 연산횟수가 달라지는 행렬곱셈으로, DP를 이용해 풀었다.

가장 좁은 구간부터 연산횟수를 구하고 저장하여 구간을 넓히며 값을 구해나갔다.

 

dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱셈연산의 최솟값 이고,

dp[i][i] = 0이다.( dp[1][1] == dp[2][2] == dp[i][i] = 0, 행렬한개로 곱셈을 하지않는다.)

예시를 통해 알아보자.

dp 2차원배열을 다음과 나타낼 수 있다.

각 행과 열은 행렬의 크기를 나타낸다.

최종적으로 dp[1][3]을 구하기 위해 작은 구간부터 칸을 채워나가보자.

 

구간의 길이가 2일때 : [1,2], [2,3]

위 2차원 배열에선 dp[1][2], dp[2][3]의 값을 구하는것이다.

 

구간의 길이가 2일땐, 순서상관없이 연산횟수가 같다.(순서는 바꾸면안된다. 행렬곱셈이 안됨)

dp[1][2] =  $5\times3\times2$ = $30$

dp[2][3] =  $3\times2\times6$ = $36$

 

 

구간의 길이가 3일때: [1,2] + 3, 1 + [2,3] 

위와 다르게 표현한 이유는 점화식으로 표현하기 위해서이다.

결국 구간 [1,2,3]의 값이 저장된 dp[1][3]을 구하는 것이지만,

[1,2] 와 [2,3]은 이미 이전에 구한뒤 저장해두었다.

 

dp[1][2] $\times$ [3]과 [1] $\times$ dp[2][3]의 결과중 최솟값을 넣으면 된다.

dp[1][2] $\times$ [3]: dp[1][2] + ($5 \times 2 \times 6$) = 90(1번행렬과 2번행렬을 곱하면 5x2 배열)

[1] $\times$ dp[2][3]: dp[2][3] + ($5 \times 3 \times 6$) = 126(2번행렬과 3번행렬을 곱하면 3x6 배열)

따라서 dp[1][3]은 더 작은값 90을 저장한다.

 

 

정리)

1. N개의 행렬이 주어지면 dp[1][N]의 값을 구한다.(dp[1][N]: 1번째행렬부터 N번째 행렬까지 연산의 최소횟수)

2. 가장작은 구간의 곱셈부터 구하고 최솟값을 저장한다.

3. 저장된 구간으로부터 더 넓은 구간의 연산횟수를 구한다.(최솟값을 비교하여 저장)

4. 최종적으로 dp[1][N]을 구한다.

 

예시: [1,2,3,4,5]

구간 2: [1,2], [2,3], [3,4], [4,5]

구간 3: [1,2,3], [2,3,4], [3,4,5]

구간 4: [1,2,3,4], [2,3,4,5]

구간 5: [1,2,3,4,5]

 

점화식은 다음과 나타낼 수 있다.

$\mathbf{dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + ((j행 \times k열 \times i+j열)(k: i와 i+j 사이의 점)} $

 

3중 for문을 이용하여 코드를 구현해보자.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: 0, count: 2), count: N+1)

// 주어진 행렬들의 행,열 저장
for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][0] = input[0]
    arr[i+1][1] = input[1]
}

// dp[i][j]: i번째부터 j번째까지 연산의 최소횟수
// 가장 좁은구간부터 구한 값을 이용해 넓은 구간의 최솟값을 구한다.
for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][0] * arr[k][1] * arr[i+j][1]))
        }
    }
}
print(dp[1][N])

 

 

배열의 크기를 무분별하게 크게 선언했다가 시간초과가 났다..

행렬들의 행,열은 곱셈을 하면 결과의 행,열이 변할 수 있어도, 값 자체가 변하진 않는다. (피연산 행렬들의 행 열을 가져옴)

(5x2와 2x3의 결과가 왼쪽행렬의 행, 오른쪽행렬의 열을 가져와 5x3이 되는것처럼)

이를 이용해 2차원배열에 저장해두었다.

 

아예 튜플로 저장하여 문제풀이를 시도했지만, 시간초과가 났다.

 

시간초과가 난 코드

import Foundation

let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var arr = Array(repeating: Array(repeating: (x: 0, y: 0), count: N+1), count: N+1)

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i+1][i+1] = (x: input[0], y: input[1])
}

for i in 1...N {
    for j in 1..<N-i+1 {
        dp[j][j+i] = Int.max
        for k in j..<j+i {
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + (arr[j][k].x * arr[j][k].y * arr[k+1][j+i].y))
            arr[j][j+i] = (x: arr[j][k].x, y: arr[k+1][j+i].y)
        }
    }
}

print(dp[1][N])