[백준] 11049번 행렬 곱셈 순서 - Java/자바

문제

문제 바로가기

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

---

접근방법

이 문제는 동적 계획법을 이용해 풀 수 있다.

각 행렬의 정보를 2차원 배열 a에 저장한다. 여기서 a[i][0]은 i번째 행렬의 행의 수, a[i][1]은 i번째 행렬의 열의 수를 의미한다.

그리고 d[i][j]를 i번째부터 j번째까지의 행렬을 곱하는 최소 연산 횟수로 정의한다.

간단히 풀이 과정을 설명하면 다음과 같다.

1. i를 1부터 N-1까지 반복하면서 d[j][j+i]를 통해 인접한 2개의 행렬부터 N개의 행렬까지 차례로 계산할 수 있도록 해준다.
2. k를 0부터 i-1까지 반복해서 j와 j+i 사이에 있는 행렬들을 나누어 계산하여 그 중 최솟값을 d[j][j+i]에 저장해준다.
3. 그리고 처음부터 마지막까지의 행렬을 곱하는 최소 횟수 d[0][N-1]를 정답으로 출력하면 된다.
   

풀이

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

public class Main {
    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.parseInt(br.readLine());
        int[][] a = new int[N][2];
        int[][] d = new int[N][N];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a[i][0] = Integer.parseInt(st.nextToken());
            a[i][1] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1; i < N; i++) {
            for(int j = 0; j < N-i; j++) {
                d[j][j+i] = Integer.MAX_VALUE;
                for(int k = 0; k < i; k++) {
                    int cnt = d[j][j+k] + d[j+k+1][j+i] + a[j][0] * a[j+k][1] * a[j+i][1];
                    d[j][j+i] = Math.min(d[j][j+i], cnt);
                }
            }
        }

        bw.write(String.valueOf(d[0][N-1]));
        bw.flush();
        bw.close();
        br.close();
    }
}