[백준] 11049번 : 행렬 곱셈 순서 (Java)

🔗 11049번 : 행렬 곱셈 순서
● Java 풀이
● 시간 제한 1초
● 메모리 제한 256 MB

문제

 

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• 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번이다.
• 같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

 

테스트 케이스

// input
6
2 4
4 6
6 1
1 2
2 3
3 5

// answer
63

/** 출처 (https://www.acmicpc.net/board/view/123487) **/
// input
4
5 4
4 3
3 2
2 1

// answer
38

/** 출처 (https://www.acmicpc.net/board/view/93742) **/
// input
5
1 10
10 1
1 10
10 1
1 10

// answer
31

// input
4
5 3
3 2
2 6
6 3

// answer
96

//input
1
2 3

// answer
0

 

풀이

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

public class Main {
    private static class Pos {
        public Pos(long r, long c) {
            this.r = r;
            this.c = c;
        }

        long r, c;
    }

    private static int N;
    private static Pos[] poses;  // 행렬을 담을 배열
    private static long[][] dp;  // 각 곱을 더할 배열


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

        N = Integer.parseInt(br.readLine());
        poses = new Pos[N];
        dp = new long[N][N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], (long) Math.pow(2, 31));
            st = new StringTokenizer(br.readLine());
            poses[i] = new Pos(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));  // 행렬 담기
        }
        
        System.out.println(findMinMultiply());
    }

    private static long findMinMultiply() {
        for (int i = 0; i < N; i++) { // i 까지
            for (int j = i - 1; 0 <= j; j--) {  // j 에서
                if (i - j == 1) {  // 무조건 결과 하나 (AB) 같은 경우
                    dp[j][i] = (poses[j].r * poses[j].c * poses[i].c);
                    continue;
                }

                dp[j][i] = Math.min(dp[j][i - 1] + (poses[j].r * poses[i].r * poses[i].c), dp[j][i]);  // (...) * n 값 찾기 ((AB)C) 같은 경우
                dp[j][i] = Math.min((poses[j].r * poses[j].c * poses[i].c) + dp[j + 1][i], dp[j][i]);  // n * (...) 값 찾기 (A(BC)) 같은 경우

                for (int k = j + 1; k < i - 1; k++) {  // 사이 계산 찾기 ((AB)(CD)) 같은 경우
                    dp[j][i] = Math.min(dp[j][k] + dp[k + 1][i] + (poses[j].r * poses[k].c * poses[i].c), dp[j][i]);
                }
            }
        }
        return dp[0][N - 1];
    }
}

 

점점 난이도가 어려워진다.

((AB)(CD)) 같은 경우를 고려하지 않고는 풀지 못하는 문제.

나는 애초에 행렬곱셈 방법 자체를 몰라서 이상하게 풀다가 4시간 정도 날렸다...

 

dfs로 풀면 시간 초과가 나므로 dp 2차원 배열에 start - end 값의 최솟값을 저장해두어야 한다.

(A(BCDE)) 같은 경우엔 (A.r * A.c * E.c) + dp[B][E]와 같이,

((ABCD)E) 같은 경우엔 (A.r * E.r * E.c) + dp[A][D]와 같이 재사용이 가능해야 한다.

그리고 위에서 말했듯이 ((ABC)(DE))와 같은 사잇값도 고려해야 한다.

2차원 배열을 찍어보며 범위별 최솟값을 손 계산과 비교하다 보면 어디가 틀렸는지 더 수월하게 찾을 수 있다.