[백준] 11049번: 행렬 곱셈 순서 (JAVA)

인간몽쉘김통통·2024년 7월 3일

다이나믹 프로그래밍 백준 알고리즘

백준

목록 보기

70/92

문제

이해

행렬끼리 곱셈을 하기 위해선 각 행렬의 열과 행 (혹은 행과 열)이 같아야 합니다.

NxM 행렬, MxK 행렬이 있다면 행렬의 곱셈 연산의 횟수는 NxMxK가 됩니다.

행과 열의 개수가 주어진 행렬 N개가 주어질 때, 곱셈 연산 횟수의 최솟값을 구하면 됩니다.

단, 행렬의 곱셈은 입력된 순서를 유지한 채 수행되어야 합니다.

접근

행렬 곱셈이 가능한 행렬 집합 A, B, C가 있을 때 가능한 경우는 ((AxB)xC) 혹은 (Ax(BxC))가 있습니다. 무엇을 먼저 곱해야 연산 횟수가 최소가 되는지 알아야 합니다.

완전탐색의 시점으로 본다면 묶어서 곱할 2개의 행렬을 항상 선택해야 합니다. nC2 x (n-1)C2 * ...... 만큼 수행해야 합니다.

n은 최대 500이기 때문에 시간적으로 불가능합니다. 따라서, 다른 탐색 방법이 필요해보입니다.

DP의 시점으로 봅시다. DP 배열을 2차원으로 첫번째 인덱스는 왼쪽 한계선, 두번째 인덱스는 오른쪽 한계선으로 취급하면 우리가 구해야 할 정답은 DP[1][N]이 되겠습니다. (1부터 N까지의 행렬 곱셈의 최소 연산 수)

그럼 DP[1][N]은 1 <= x <= N 일때 DP[1][x] + DP[x][N] + data[1][0] x data[x][1] x data[N][1]이 됩니다. 가능한 x 중에서 최솟값을 선택해 DP[1][N]을 결정하면 됩니다.

풀이

bottom-up 방식으로 코드를 작성해보겠습니다.

    for (int i = 1; i <= N; i++) {
      for (int j = i - 1; j >= 1; j--) {
        dp[j][i] = INF;
        for (int k = j; k < i; k++) {
          int value = dp[j][k] + dp[k + 1][i] + (data[j][0] * data[k][1] * data[i][1]);
          dp[j][i] = Math.min(dp[j][i], value);
        }
      }
    }

j는 왼쪽 한계선, i는 오른쪽 한계선입니다. i는 최대 N까지 가능하고 j는 i-1부터 1까지입니다.

j가 i-1부터 수행되는 이유는 DP를 bottom up 방식으로 수행할 때 가장 작은 단위를 먼저 해야하기 때문입니다. j를 i-1부터 계산하면서 그 다음 i-2, i-3... 에서 현재의 값을 활용하도록 합니다. (메모이제이션)

코드

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

public class Main {
  static final int INF = 1_000_000_000;
  static StringTokenizer st = null;
  static int[][] data;
  static int N;
  static int[][] dp;

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

    N = Integer.parseInt(br.readLine());

    dp = new int[N + 1][N + 1];
    data = new int[N + 1][2];
    for (int i = 1; i <= N; i++) {
      st = new StringTokenizer(br.readLine());
      int r = Integer.parseInt(st.nextToken());
      int c = Integer.parseInt(st.nextToken());

      data[i][0] = r;
      data[i][1] = c;
    }

    for (int i = 1; i <= N; i++) {
      for (int j = i - 1; j >= 1; j--) {
        dp[j][i] = INF;
        for (int k = j; k < i; k++) {
          int value = dp[j][k] + dp[k + 1][i] + (data[j][0] * data[k][1] * data[i][1]);
          dp[j][i] = Math.min(dp[j][i], value);
        }
      }
    }

    System.out.println(dp[1][N]);
  }
}