[java]행렬 곱셈 순서 - 백준11049

문제

• 행렬 곱셈 순서(백준11049)

풀이

문제 해석을 하자면,

• 행렬 곱의 최소 연산수를 구하는 문제이다.

풀이

• 연쇄 행렬곱셈 DP 를 참고

코드

package ProblemSolution.DP_Detail;

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

/**
 * if i==j, 0
 * if i<j, min(M[i][k] + M[k+1][j] + d_i-1*d_k*d_j) => i<=k<=j-1
 * A_i 차원 : d_i-1*di
 * i개 순서로 행렬을 입력받고, i부터 j행렬 까지 곱의 최소 연산수를 구해가는게 D[i][j] 이다.
 *
 * 처음 제출 실패. 원인은 대각선으로 계산(접근)해나가지 않아서!!
 * 대각선 접근 로직 잘 기억
 */
public class 행렬곱셈순서_BOJ11049 {
    public static List<Matrix> inArr = new ArrayList<>();
    public static long[][] D = new long[505][505];

    public static void main(String[] args) throws IOException {
        inArr.add(new Matrix(0,0)); // 0번째 칸은 안쓰려고 임의로 쓰레기값 삽입
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int N = Integer.parseInt(br.readLine());
        for(int i = 0 ; i<N; i++) {
            stk = new StringTokenizer(br.readLine(), " ");
            long r = Long.parseLong(stk.nextToken()); // row size
            long c = Long.parseLong(stk.nextToken()); // col size
            inArr.add(new Matrix(r,c)); // 총 N개 행렬 기록
        }
        // run
        // if i==j, 0 은 전역 배열로 선언함으로써 이미 0 으로 초기화
        // 바로 if i<j 로 넘어간다. => 대각선으로 접근해서 계산해나갈 것이다.
        // diagonal 을 이용해서 2차원 배열을 대각선으로 접근해나간다.
        // 예로 i : 1,2,3,4,5 => 1,2,3,4,5 => 1,2,3,4,5 => ...
        // 예로 j : 2,3,4,5 => 3,4,5 => 4,5 => ...
        for(int diagonal = 1; diagonal<N; diagonal++) {
            for(int i = 1; i<= N-diagonal; i++) {
                int j = i + diagonal;
                for(int k = i; k<=j-1; k++) { // i<=k<=j-1
                    long d1 = inArr.get(i).r; // d_i-1
                    long d2 = inArr.get(k).c; // d_k
                    long d3 = inArr.get(j).c; // d_j
                    long d123 = d1 * d2 * d3;
                    if (k == i) D[i][j] = Math.min(2100000000, D[i][k] + D[k + 1][j] + d123);
                    else D[i][j] = Math.min(D[i][j], D[i][k] + D[k + 1][j] + d123);
                }
            }
        }
        // output
        System.out.println(D[1][N]);
    }
    static class Matrix {
        long r; long c;
        public Matrix(long r, long c) {
            this.r = r; this.c = c;
        }
    }
}

느낀점

처음 제출 실패.
원인은 대각선으로 계산(접근)해나가지 않아서!!

대각선 접근 로직 잘 기억