[BOJ] BOJ 11049번 '행렬 곱셈 순서' (Java)

[백준 11049번 '행렬 곱셈 순서']

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

 

[접근방식]

다이나믹 프로그래밍을 이용하여 해결한다.

DP 배열의 정의는 다음과 같다.

"dp[i][j] : i번째 행렬부터 j번째 행렬까지 최소 곱셈 연산수"

 

작은 집합부터 계산해 나가 궁극적으로 0 ~ n-1 까지의 행렬의 최소 곱셈 연산수를 구한다.

 

'''

곱셈 연산 단위 : 2개 - [(0, 1), (1, 2), (2, 3), (3, 4), ... , (8, 9)]
곱셈 연산 단위 : 3개 - [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), ... , (7, 8, 9)]

 

...

 

곱셈 연산 단위 : 10개 - [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)]

'''

 

위와 같이 모든 경우를 세세하게 구해 궁극적으로 0 ~ 9 까지 행렬 곱연산수의 최솟값을 구한다.

 

 

"dp[i][j]" 는 다음과 같은 연산으로 정의된다. (i <= k <= j)

"i ~ j 행렬까지의 최소 곱셈 연산수"

= "i ~ k 행렬까지의 최소 곱셈 연산수" 

+ "k+1 ~ j" 행렬까지의 최소 곱셈 연산수"

+ "위 두 행렬의 최소 곱셈 연산수"

 

[Java 코드]

/**
 * BOJ_11049 행렬 곱셈 순서
 * https://www.acmicpc.net/problem/11049
 * keyword - 
 */

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    //dp 정의 : i번째 행렬부터 j번째 행렬까지의 곱의 최소 연산수
    int[][] dp = new int[N][N];

    for (int len = 1; len < N; len++) { //곱셈 연산 단위 -> index 차이
      for (int i = 0; i + len < N; i++) {
        int j = i + len;
        dp[i][j] = Integer.MAX_VALUE;

        /**
         * i ~ k 까지 곱셈 연산 수
         * k+1 ~ j 까지 곱셈 연산 수
         * 두 행렬의 곱셈 연산 수
         */
        for (int k = i; k < j; k++) {
          int cost = dp[i][k] + dp[k + 1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1];
          dp[i][j] = Math.min(dp[i][j], cost);
        }
      }
    }


    //0 ~ n-1 까지 곱연산수 최솟값
    System.out.println(dp[0][N - 1]);
  }

}

 

[Rewind]

1. 어려웠던 점

- 문제 해결 접근 방식을 제대로 알지 못했다.

- DFS 방식을 통해 모든 경우를 탐색하는 방식을 생각했지만, 비효율적인것 같아 철회했다.

- DP 배열의 정의를 생각해내지 못했고, 그 결과로 문제 역시 해결하지 못했다.

- "곱셈 연산 단위" 라는 것을 이해하지 못했다.

- DP 해결 방식의 기본적인 정의인 "문제를 가장 작은 단위로 나눠 해결하고, 이를 저장하여 불필요한 연산을 줄인다." 라는 것을 잊었다.

 

2. 알게된 점

- DP문제의 새로운 유형을 알게 되었다.

- DP문제의 정의를 다시 일깨웠다.

 

3. 개선방안

- 잘모르겠다.