[BOJ] 11049 행렬 곱셈 순서 - JAVA

1. 문제

11049번: 행렬 곱셈 순서

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.
- AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
- BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

---

2. 풀이

ABCD...Z까지 행렬곱셈을 한다고 했을 때, start=A, end=Z다.

그 사이에서 mid를 옮겨가며 앞묶음과 뒤묶음으로 나눠 곱셈을 생각한다.

(앞)*(뒤)로 나눴을 때, 그 연산 횟수는 앞묶음 연산횟수 + 뒷묶음 연산횟수 + (앞x뒤 연산횟수)가 된다.

여기서 앞, 뒤 각각의 연산횟수는 dp에 저장되어 있다.

앞x뒤 연산횟수를 새로 구해야 하는데, 이 값은

"앞묶음의 가장 처음 행렬 행 숫자 x 앞 묶음의 가장 뒷 행렬의 열 숫자(=뒷 묶음의 가장 처음 행렬 행 숫자) x 뒷 묶음의 가장 뒷 행렬의 열 숫자"

로 구할 수 있다.

 

start부터 end 사이를 mid로 쪼개 연산횟수를 구하기 때문에 거리(end-start)순으로 dp를 채워나간다.

mid를 옮겨가면서 탐색할 때, min값을 골라 저장하므로 dp의 초기값을 Integer.MAX_VALUE로 한다.

초기값으로 배열을 채우면서 dp[i][i]를 0으로 저장한다. 자기 자신을 곱하지 못하기 때문이다. (연산횟수 0)

 

탐색이 끝난 후에는 dp[0][N-1]을 출력한다.

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

public class BOJ_11049_행렬곱셈순서 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[][] arr = new int[N][2];
      StringTokenizer st;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         arr[i][0] = Integer.parseInt(st.nextToken());
         arr[i][1] = Integer.parseInt(st.nextToken());
      }

      int[][] dp = new int[N][N];
      for(int i=0;i<N;i++){
         Arrays.fill(dp[i], Integer.MAX_VALUE);
         dp[i][i] = 0;
      }

      int end;
      for(int len=1;len<N;len++){
         for(int start=0;start<N-len;start++){
            end = start+len;
            int tmp = arr[start][0]*arr[end][1];
            for(int mid = start;mid<end;mid++){
               dp[start][end] = Math.min(dp[start][end],
                     dp[start][mid]+dp[mid+1][end]+tmp*arr[mid][1]);
            }
         }
      }

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

---

3. 결과

arr[start][0]*arr[end][1]부분이 중복계산되는 것 같아서 tmp로 뺐는데 오히려 시간이 더 걸렸다. 이유는 모르겠다!