BOJ G3 11049 행렬 곱셈 순서 JAVA

11049번: 행렬 곱셈 순서

---

문제 읽기

일단 문제를 처음 봤을 때 어제 푼 문제와 비슷하다고 느꼈다. 어제는 아래 파일 합치기 문제를 풀었었다.

BOJ G3 11066 파일 합치기 JAVA

그래서 비슷하게 DP로 접근했다!

---

문제 풀기

파일 합치기를 보고 오면 알겠지만 이 문제도 중복되는 연산이 많이 발생하기 때문에 DP로 해결이 가능하다.

즉 다음과 같이 이차원 DP로 표현할 수 있다.

DP[i][j] : i부터 j까지 행렬 곱의 최소 비용

 

또한 DP배열의 타입은 다음과 같은 Matrix라는 class를 정의하여 사용했다.

static class Matrix{
        int r, c;
        int cost;
        public Matrix(int r, int c, int cost){
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
}

 

해당 지점까지 곱했을 때의 결과 행렬 크기를 나타내는 r, c, 그리고 해당 지점의 행렬 곱의 최소 비용을 나타내는 cost이다.

 

예시

간단하게 수식으로 예를 들어보자.

 

A(5x3)이라는 하나의 행렬을 모두 곱하는 비용은 얼마일까?

0이다. 곱할 행렬이 없기 때문이다.

즉, DP[i][i] = new Matrix(5, 3, 0)이 된다. (로직 작성 시 이 값으로 초기화해주어야 한다.)

 

 

A(5x3), B(3x2)라는 두 개의 행렬을 곱하는 비용은 얼마일까? 5x3x2이다.

DP[A][B] = new Matrix(5, 2, 30)이므로,

즉,

DP[i][i+1] = new Matrix(matrix[A].r, matrix[B].c, matrix[A].r * matrix[B].r * matrix[B].c)이면서

DP[i][i+1] = new Matrix(DP[A].r, DP[B].c, DP[A].r * DP[B].r * DP[B].c)이다. (여기서 matrix 배열은 입력 받은 행렬 정보를 저장하는 배열이다)

우리는 DP를 계속 반복해서 사용하기 때문에, 아래 식을 기억하자.

 

 

A(5x3), B(3x2), C(2x6)인 세 개의 행렬이 있다고 가정했을 때, 행렬의 곱 ABC를 구하는 경우의 수를 생각해보자.

• ((AB)C) = 5x3x2 + 5x2x6 = 30 + 60 = 90
• (A(BC)) = 3x2x6 + 5x3x6 = 36 + 90 = 126

위와 같이 두 가지 경우의 수가 나온다. 이 둘 중에서 최소인 값을 DP[A][C]에 저장할 수 있을 것이다.

식으로 나타내면,

• DP[A][C] = DP[A][B].cost + DP[A][B] x DP[C][C]
• DP[A][C] = DP[B][C].cost + DP[A][A] x DP[B][C]

이렇게 나타낼 수 있다.

일반화하면,

• DP[i][j] = DP[i][s] + DP[i][s] x DP[j][j]
• DP[i][j] = DP[s][j] + DP[i][i] x DP[s+1][j]

이렇게 나온다. 여기까지 보면 뭔가 알 것 같은데 애매할 수 있다.

 

 

마지막으로 A(5x3), B(3x2), C(2x6), D(6x3) 네 개의 행렬이 있다고 가정했을 때, 행렬의 곱 ABCD를 구하는 경우의 수를 생각해보자.

• A(BCD) = DP[A][A] x DP[B][D] + DP[B][D].cost
• (AB)(CD) = DP[A][B] x DP[C][D] + DP[A][B].cost + DP[C][D].cost
• (ABC)D = DP[A][C] x DP[D][D] + DP[A][B].cost

위와 같이 세 가지 경우의 수가 나온다.

두 번째 경우를 보면 일반화 식이 완벽하게 나온다. 이때까지는 더해주는 값이 하나였지만, 실은 DP[i][i].cost = 0이기 때문에 생략된 것이다.

 

즉, 점화식을 다음과 같이 세울 수 있다.

DP[i][j] = DP[i][s] x DP[s+1][j] + DP[i][s].cost + DP[s+1][j].cost

(j : 0~N-1, i : j-1~0, s : i~j-1) - 범위에 관한 상세한 설명은 파일 합치기 포스팅 참고

 

이를 이용하여 문제를 해결하면 된다.

---

코드

package ps.DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G3_11049_행렬곱셈순서 {
    static class Matrix{
        int r, c;
        int cost;
        public Matrix(int r, int c, int cost){
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());

        Matrix[] matrix = new Matrix[N];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            matrix[i] = new Matrix(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), 0);
        }
        Matrix[][] dp = new Matrix[N][N];
        for (int j = 0; j < N; j++){
            for (int i = j; i >= 0; i--){
                if (i == j){ //대각선엔 자기 자신으로 채워주고 끝내기
                    dp[i][j] = new Matrix(matrix[i].r, matrix[i].c, 0);
                    continue;
                }
                //다른 곳에서는 계산! : i와 j사이의 행렬 곱 연산의 합의 최솟값
                dp[i][j] = new Matrix(-1, -1, Integer.MAX_VALUE); //임의의 값으로 초기화
                for (int k = i; k < j; k++){ //i~j-1
                    Matrix newMat = multiple(dp[i][k], dp[k+1][j]);
                    newMat.cost += dp[i][k].cost + dp[k+1][j].cost;
                    if (dp[i][j].cost > newMat.cost){
                        dp[i][j] = newMat;
                    }
                }
            }
        }
        System.out.println(dp[0][N-1].cost);
    }

    private static Matrix multiple(Matrix mat1, Matrix mat2) {
        return new Matrix(mat1.r, mat2.c, mat1.r * mat1.c * mat2.c);

    }
}