백준 11049 (행렬 곱셈 순서) <구간 DP>

문제

11049번: 행렬 곱셈 순서

N개의 행렬이 주어지면 주어진 순서대로 행렬 곱을 할때 가장 적은 연산횟수를 구하는 문제이다.

예를 들어 A = (5, 3), B = (3, 2), C = (2, 6) 으로 주어졌다고 하면

• 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번이다.

즉 연산의 순서에 따라 연산 횟수에서 차이가 나온다.

---

어떤식으로 dp의 점화식을 쓸까 고민하다. 구간으로 나눠서 최소 연산을 저장하기로 했다.

즉, dp[i][j] = 행렬 i번째 부터 행렬 j번째까지 곱했을 때 최소 연산횟수이다.

코드를 바로 살펴보자.

for(int i=1;i<n;i++){ //구간 범위 (i ~ j)
      for(int j=0;i+j<n;j++){ //시작점 (j)
          dp[j][i+j] = Integer.MAX_VALUE;
          for(int k = j;k<i+j;k++){ // 나누는 구간(j ~ k, k+1 ~ i+j)
              dp[j][j+i] = Math.min(dp[j][j+i], dp[j][k] + dp[k+1][i+j]+matrix[j][0] * matrix[k][1]*matrix[i+j][1]);
          }
      }
}

출처 : https://cocoon1787.tistory.com/318

예를 들어 i = 4, j = 3, k = 4라면 위와 같은 그림이 된다.

3~4 구간의 연산과 5 ~ 7구간의 연산의 합과 N * M * K를 더해야 한다.

N = dp[3][0]

M = dp[4][1]

K = dp[7][1] 

입니다.

---

전체 코드입니다.

public class Main {
    private static int[][]matrix;
    private static int[][]dp;

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


        int n = Integer.parseInt(st.nextToken());

        matrix = new int[n][2];
        dp = new int[n][n];

        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());
        }

        for(int i=1;i<n;i++){ //구간 범위
            for(int j=0;i+j<n;j++){ //시작점
                dp[j][i+j] = Integer.MAX_VALUE;
                for(int k = j;k<i+j;k++){
                    dp[j][j+i] = Math.min(dp[j][j+i], dp[j][k] + dp[k+1][i+j]+matrix[j][0] * matrix[k][1]*matrix[i+j][1]);
                }
            }
        }

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