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

 

 

BOJ 11049 - 행렬 곱셈 순서 (https://www.acmicpc.net/problem/11049)

 

01. 🔎 문제 탐색

N: 행렬의 개수 $(1 \leq N \leq 500)$
r, c: 행렬의 크기 $(1 \leq r, c \leq 500)$  

• 행렬의 곱을 수행했을 때, 순서에 따라 연산 횟수가 달라지게 되는데, 연산 횟수가 가장 낮아지는 순서로 계산하였을 때 나오는 최소 연산 횟수를 출력

01-1. 알고리즘 선택 & 시간 복잡도

• 이전 행렬 곱의 연산 횟수를 다음 연산 횟수에 이용해 사용할 수 있으므로, DP로 해결할 수 있음
• dp배열은 2차원 배열로 나타낼 수 있으며, i와 j는 i번째 행렬부터 j번째 행렬까지 행렬 곱을 진행했을때, 최소 연산 횟수를 담음
• i부터 j까지 범위의 행렬 곱 최소 연산 횟수 dp[i][j]는 아래와 같은 점화식으로 나타낼 수 있음

$dp[i][j] = min_{k=i}^{j-1}(dp[i][k] + dp[k+1][j] + cost)$

$cost = row[i] * col[i] * col[j]$

02. 📝 코드 설계하기

1. 행렬의 개수 N과 행렬의 정보 r, c를 순차적으로 입력
   1. 입력 시, dp[i][i]는 아직 연산이 없는 상태이므로 연산 횟수는 0이며, r과 c를 저장
2. dp[i][j]에 대하여 순차적으로 탐색 시작
   1. k(1~j-1)를 순차적으로 탐색하며, dp[i][k] + dp[k+1][j] + cost를 계산하여 나온 최솟 값을 dp[i][j]의 최솟값으로 함
      (이 때, cost는 두 행렬 dp[i][k]과 dp[k+1][j]을 행렬 곱한 연산 횟수를 나타냄)
3. dp[1][N]는 1~N까지 행렬을 행렬 곱한 최소 연산 횟수를 가지고 있으므로, 출력

03. 🛠️ 시도별 수정

1회차

---

04. 🗝️ 정답 코드

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

public class boj11049 {

  public static class Matrix{
    private int r, c;
    private long value;

    Matrix(int r, int c, long val){
      this.r = r;
      this.c = c;
      this.value = val;
    }

    void setMatrix(int r, int c, long val){
      this.r = r;
      this.c = c;
      this.value = val;
    }

    long getValue(){
      return this.value;
    }
    int getRow(){
      return this.r;
    }
    int getCol(){
      return this.c;
    }
  }

  public static long mult(Matrix a, Matrix b){ 
    return a.getRow() * a.getCol() * b.getCol() + a.getValue() + b.getValue(); 
  }
  

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

    int N = Integer.valueOf(br.readLine());
    int r, c;
    Matrix[][] dp = new Matrix[N+1][N+1];

    for(int i = 1; i <= N; i++){
      st = new StringTokenizer(br.readLine());
      r = Integer.valueOf(st.nextToken());
      c = Integer.valueOf(st.nextToken());

      dp[i][i] = new Matrix(r, c, 0);
    }

    for(int i = 1; i < N; i++){
      for(int j = 1; j <= N-i; j++){
        long curValue = mult(dp[j][j], dp[j+1][j+i]);
        int curRow = dp[j][j].getRow(), curCol = dp[j+1][j+i].getCol();

        dp[j][j+i] = new Matrix(curRow, curCol, curValue);
        for(int k = 1; k <= i-1; k++){
          curValue = mult(dp[j][j+k], dp[j+k+1][j+i]); 
          curRow = dp[j][j+k].getRow(); curCol = dp[j+k+1][j+i].getCol();

          if(dp[j][j+i].getValue() > curValue)
            dp[j][j+i].setMatrix(curRow, curCol, curValue);
        }
      }
    }

    bw.write(dp[1][N].getValue() + "\n");

    bw.flush();
    bw.close();
    br.close();
  }
}