BOJ_11049 : 행렬 곱셈 순서

👉 문제링크

---

---

🔸 문제 분석 🔸

• N개의 행렬을 곱셈 계산하려고 한다. 행렬의 곱은 곱셉 연산의 순서에 따라 연산 횟수가 달라진다.
• 행렬곱 연산의 최소값을 출력한다.

🔸 문제 풀이 🔸

• 다이나믹 프로그래밍으로 풀이할 수 있다.
• dp배열로 int형 2차원 배열을 만들어 dp[i][j] : i ~ j 번 행렬 곱의 연산 수 최소값을 저장한다.
• i ~ j 의 크기 size를 2 이상부터 N 이하까지 늘려가며 dp 배열을 채워간다.
• i == j (size == 1) 일 때, dp[i][j]는 0이다.
• 최대 int형만 사용된다고 문제에서 나타내주었다.

🔸 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] matrix = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            matrix[i][0] = Integer.parseInt(st.nextToken());
            matrix[i][1] = Integer.parseInt(st.nextToken());
        }

        // Dynamic Programming
        int[][] dp = new int[N][N];

        for (int gap = 2; gap <= N; gap++) { // 인덱스 차이 크기
            for (int start = 0; start <= N - gap; start++) { // 시작 인덱스

                int end = start + gap - 1; // 끝 인덱스
                dp[start][end] = Integer.MAX_VALUE;

                for (int i = start; i < end; i++) { // 자르기 인덱스
                    dp[start][end] = Math.min(dp[start][end],
                            dp[start][i] + dp[i + 1][end] + matrix[start][0] * matrix[i][1] * matrix[end][1]);
                }
            }
        }

        // Output
        bw.write(Integer.toString(dp[0][N - 1]));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 행렬의 가로 세로 크기를 matrix 배열에 저장한다.
• N * N 크기의 dp 배열을 만들어 다음과 같은 계산으로 채워간다.
  • 시작 인덱스와 끝 인덱스의 차이를 2부터 N까지 늘려가며 계산한다.
  • dp[시작 인덱스][끝 인덱스] 에 최소값을 채워간다. 여기서 각 인덱스를 기준으로 잘라 보며 계산한다.
  • 인덱스를 잘랐을때 행렬 곱은 matrix[start][0] * matrix[i][1] * matrix[end][1] 형태로 계산 횟수를 카운트 할 수 있다.
    (앞 행렬의 행, 중간 자르기 행렬의 열, 뒷 행렬의 열 크기의 곱)
• 모든 dp 배열을 채웠으면, 구하고자 했던 0 ~ (N-1) 의 행렬곱 연산 최소값인 dp[0][N-1] 를 출력한다.

---

🔸 end 🔸

• 어려웠던 문제였다. dp인건 어느정도 알았지만, 2차원 배열로 나타내고자 하는 아이디어가 떠오르지 않아서 점화식 부분을 검색해본 뒤 풀이할 수 있었다.
• 점화식 부분을 명확히 쓰기 어려운데, 범위를 잘라서 연산수를 계산하고, 두 잘린 행렬곱을 서로 곱할때의 연산 횟수만 더해주면 된다. 그림으로 그려보니 바로 이해가 되어서 한번에 통과할 수 있었다.