백준 11049번 : 행렬 곱셈 순서 | JAVA

골드 3

 

📌 알고리즘 선택

문제를 읽고 행렬의 크기를 직접 곱해보면서, 이 문제는 중복된 계산이 많고 범위를 지정해서 값을 기억해야 하기에 무조건 2차원 dp로 풀어야겠다는 생각이 들었다. 그런데 구현 하기가 너무 어려웠다.. 이런저런 생각을 하다보니 트리까지도 그리게 되었는데 행렬의 크기를 담은 배열을 마음대로 수정하다보니 마음처럼 결과가 안나오더라.. 아직 좀더 연습이 필요한 것 같다!

 

---

📌 풀이

😥😥

아쉬운 마음에 올려보는 ,, 나의 트리 ,, 재귀로 풀어보고 싶은데 재도전 해봐야겠다.

 

 

아무튼 결국은 2차원 배열을 사용한 dp로 풀었으니,, 해당 풀이를 설명해보자.

이 문제에서 중요한 것은 dp[i][j]에 값을 채워나가는 것인데,

dp[i][j]는 i번째 행렬에서 j번째 행렬까지의 크기의 곱 중 최솟값을 담는다.

 

아래의 코드에서, matrixSolution() 함수 안의 첫번째 for문에서는 인접한 두 개의 행렬의 크기의 곱을 저장해준다.

인접한 두 행렬의 크기의 곱은 값이 하나이므로 바로 저장 가능하기에 분리해준다.

 

두번째 for문에서는 gap의 초기값을 2로 두어, i번째 행렬부터 i+gap번째 행렬까지의 크기의 곱을 계산해줄 수 있는데,

해당 범위에서 k라는 값을 기준으로 범위를 나누어 비교해야 한다.

어디에서 나누는지에 따라 값이 달라지기 때문이다.. (매우 당연)

이때 dp[i][j]에는 기존 dp[i][j] 값과 dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1] 중 더 작은 값을 저장한다.

 

dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1] 

위의 식을 만들기가 가장 어려웠는데,

두 행렬 dp[i][k]와 dp[k+1][j]가 만들어지면서 계산된 곱의 합과 그 두 행렬의 크기의 곱을 더해준다고 생각하면 된다.

 

그래서 결과값으로 dp[0][N-1]을 출력하면 된다.

 

---

📌 코드

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

public class Main {

    static int N;
    static int[][] matrix;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 행렬 개수

        // 행렬 입력
        matrix = new int[N][N];
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            matrix[i][0] = Integer.parseInt(st.nextToken());
            matrix[i][1] = Integer.parseInt(st.nextToken());
        }

        // 결과 출력
        int result = matrixSolution();
        System.out.println(result);

    }

    public static int matrixSolution() {

        int[][] dp = new int[N][N];

        // 인접한 두 행렬의 곱을 계산해서 dp에 저장
        for(int i = 0; i < N - 1; i++) {
            dp[i][i+1] = matrix[i][0] * matrix[i][1] * matrix[i+1][1];
        }

        // 인접하지 않은 두 행렬의 곱을 계산해서 dp에 저장
        for(int gap = 2; gap < N; gap++) {
            for(int i = 0; gap + i < N; i++) {
                int j = i + gap;
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]);
                }
            }
        }

        return dp[0][N-1];

    }

}

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

11049번: 행렬 곱셈 순서