[11049] 행렬 곱셈 순서

✔ 행렬 곱셈 순서

[백준 11049]

문제 분석하기

행렬의 개수 N이 주어지고, 1 ~ N개를 모두 곱햇을 때 최소 연산 횟수를 구해야하므로

만약 1 ~ N - 1, 2 ~ N, 3 ~ N - 2 등 N을 제외한 모든 부분 구역을 1개의 행렬로 만드는데 필요한 최소 연산 횟수를 알 수 있다면

이를 바탕으로 1 ~ N 구역의 최소 연산 횟수를 구할 수 있음

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i][j]는 i ~ j 구간의 행렬을 합치는데 드는 최소 연산 횟수
2.  점화식을 구함
   • 행렬 구간에 행렬이 1개일 때 0을 리턴
   • 행렬 구간에 행렬이 2개일 때 '앞 행렬의 row 값 * 뒤 행렬의 row 값 * 뒤 행렬의 column값'을 리턴
   • 행렬 구간에 행렬이 3개 이상일 때는
     Math.min(min, D[s][i] + D[i + 1][e] + a(s 행렬의 row * i + 1 행렬의 row * e 행렬의 column))
   • 1 ~ N - 1까지 합친 행렬 D[1][N - 1], N번째 행렬 D[N][N]의 값을 안다고 가정할 경우
     이때 1개의 행렬로 합치는데 드는 횟수는 D[1][N - 1] + D[N][N] + a(두 행렬을 합치는데 드는 값)
   • 예) 2 x 3과 3 x 6 행렬이 있다면 a = 2 x 3 x 6 = 36
3.  점화식으로 D 배열을 채운 후 행렬 곱셈 연산 횟수의 최솟값을 출력

예) 5 * 3, 3 * 2, 2 * 6

D[1][2] 5 * 3과 3 * 2 = 5 * 3 * 2 = 30	D[3][3] 2 * 6 = 0	30 + 0 + a = 30 + 0 + 5 * 2 * 6 = 90
D[1][1] 5 * 3 = 0	D[2][3] 3 * 2와 2 * 6 = 3 * 2 * 6 = 36	0 + 36 + a =0 + 36 + 5 * 3 * 6 = 126

1.  

슈도코드 작성하기

D[i][j] (i ~ j번째 행렬까지 최소 연산 횟수를 저장하는 배열)
N(행렬 개수)
Matrix M[N](행렬 저장 클래스 배열)
D 배열 초기화 (-1로 저장하기)
행렬 데이터 저장하기
execute(1, N)
정답 출력하기

int execute(s, e) {
    result(결괏값)
    if(이미 계산한 구역일 때) D[i][j] 값 바로 리턴
    if(1개 행렬일 때) 연산 횟수 0 리턴
    if(행렬 2개일 때) 2개 행렬 연산값 리턴
    if(행렬 3개 이상일 때) {
        for(i -> s ~ e) {
            execute(s, i) + execute(i + 1, e) + 앞뒤 구간의 행렬을 합치기 위한 연산 횟수
        }
    }
}
class Matrix {
    x(행의 개수)
    y(열의 개수)
}

코드 구현하기

/**
 * 11049) 행렬_곱셈_순서
 */
public class D094_11049 {
    static int N;
    static int[][] D;
    static Matrix[] M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(행렬 개수)
        N = sc.nextInt();
        // M(행렬 저장 클래스 배열)
        M = new Matrix[N + 1];
        // D[i][j] (i ~ j번째 행렬까지 최소 연산 횟수를 저장하는 배열)
        D = new int[N + 1][N + 1];
        // D 배열 초기화
        for (int i = 0; i < D.length; i++) {
            for (int j = 0; j < D.length; j++) {
                D[i][j] = -1;
            }
        }
        // 행렬 데이터 저장하기
        for (int i = 1; i <= N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            M[i] = new Matrix(x, y);
        }
        // 정답 출력하기
        System.out.println(execute(1, N));
    }

    private static int execute(int s, int e) {
        // result(결괏값)
        int result = Integer.MAX_VALUE;
        // 이미 계산한 구역일 때
        if (D[s][e] != -1)
            // D[i][j] 값 바로 리턴
            return D[s][e];
        // 1개 행렬일 때
        if (s == e)
            // 연산 횟수 0 리턴
            return 0;
        // 행렬 2개일 때
        if (s + 1 == e)
            // 2개 행렬 연산값 리턴
            return M[s].x * M[s].y * M[e].y;
        // 행렬 3개 이상일 때 (재귀 형태로 구현)
        for (int i = s; i < e; i++)
            // execute(s, i) + execute(i + 1, e) + 앞뒤 구간의 행렬을 합치기 위한 연산 횟수
            result = Math.min(result, M[s].x * M[i].y * M[e].y + execute(s, i) + execute(i + 1, e));
        return D[s][e] = result;
    }
}

// 행렬 정보 저장하기
class Matrix {
    // x(행의 개수)
    int x;
    // y(열의 개수)
    int y;

    Matrix(int x, int y) {
        this.x = x;
        this.y = y;
    }
}