11049번 - 행렬곱셈순서(dp)

문제:

 

풀이:

행렬곱셈부터 소개하자면 5x3 행렬과 3x2 행렬이 곱해지려면 5x3x2의 연산이 필요하며, 그 결과 5x2행렬이 만들어진다.

같은 원리로 3x2행렬과 2x6 행렬이 곱해지려면 3x2x6의 연산이 필요하며, 그 결과 3x6행렬이 만들어진다.

 

(5 3) (3 2) (2 6) (6 1) (1 4)의 행렬이 주어졌다고 예시를 들고 그 연산과 결과에 대해 설명하겠다.

바로 옆에 붙은 행렬끼리의 연산 횟수부터 구해보겠다.

1. 행렬이 2개일때 최소 연산 횟수
   

   5 3	3 2	2 6	6 1	1 4
   연산 횟수	5 x 3 x 2	3 x 2 x 6	2 x 6 x 1	6 x 1 x 4
   만들어진 행렬	5 2	3 6	2 1	6 4

   기본적인 행렬 곱셈 방법의 결과 연산 횟수와 새로운 행렬이 나왔다. 이제 위 행렬을 이용해보자
2. 행렬이 3개일때 최소 연산 횟수
   행렬이 3개일때 최소 연산 횟수를 구하기 위해서는 위의 표를 잘 이용해야 한다. 먼저 위의 표를 바꿔주자
   

   0	1	2	3	4	5
   5	3	2	6	1	4

   가장 처음 행렬 제외하고는 모두 지금 행렬의 처음 수와 이전 행렬의 마지막 수가 동일할 것이다.
   

   0	1	2	3	4	5
   초기 행렬	5 3	3 2	2 6	6 1	1 4
   5	3	2	6	1	4
   행렬 2개		5 x 3 x 2	3 x 2 x 6	2 x 6 x 1	6 x 1 x 4
   만들어진 행렬		5 2	3 6	2 1	6 4
   행렬 3개			5 x 3 x 2 + 5 x 2 x 6 vs 5 x 3 x 6 + 3 x 2 x 6	3 x 2 x 6 + 3 x 6 x 1 vs 3 x 2 x 1 + 2 x 6 x 1	2 x 6 x 1 + 2 x 1 x 4 vs 2 x 6 x 4 + 6 x 1 x 4
   만들어진 행렬			5 6	3 1	2 4

   위 결과를 분석해보자.
   
   • 앞의 2개의 행렬을 먼저 계산했을 때와 뒤의 2개의 행렬을 먼저 계산했을 때를 비교함,
   • 계산 결과에 상관없이 만들어진 행렬은 (배열[i-3], 배열[i])임,
     행렬 2개를 계산했을때는 (배열[i-2], 배열[i]) 였던걸 보면, 연속성이 분명 있음.
   • 계산식 또한 규칙이 있음, 이전 계산 결과에 지금 새로운 계산 결과를 더한 값을 비교해주는 중
3. 행렬이 4개일때 최소 연산 횟수
   규칙성을 완벽하게 찾기 위해 한번 더 과정을 보자.
   다 쓰기에는 번거로우므로 하나만 더 작성해보겠다.
   

   0	1	2	3	4	5
   초기 행렬	5 3	3 2	2 6	6 1	1 4
   5	3	2	6	1	4
   행렬 2개		5 x 3 x 2	3 x 2 x 6	2 x 6 x 1	6 x 1 x 4
   만들어진 행렬		5 2	3 6	2 1	6 4
   행렬 3개			5 x 3 x 2 + 5 x 2 x 6 = 90	3 x 2 x 1 + 2 x 6 x 1 = 18	2 x 6 x 1 + 2 x 1 x 4 = 20
   만들어진 행렬			5 6	3 1	2 4
   행렬 4개			사용된 행렬
   3 : 1			5 6 6 1	5 x 3 x 2 + 5 x 2 x 6 + 5 x 6 x 1 = 120
   2 : 2			5 2 2 1	5 x 3 x 2 + 5 x 2 x 1 + 2 x 6 x 1 = 52
   1 : 3			5 3 3 1	5 x 3 x 1 + 3 x 2 x 1 + 2 x 6 x 1 = 33
   				5 1	3 4

   중복되는 부분을 색칠해놓았다.
   이전의 계산 결과를 계속해서 사용하는 것을 보면, dp를 활용한 풀이가 효과적일 듯 하다.
   각각의 점화식은 세우기 위해 배열을 작성해보겠다.
   arr
   

   5

   3

   2

   6

   1

   4

   dp
   

   	0	1	2	3	4	5
   0	0	0	0	0	0	0
   1	0	0	0	0	0	0
   2	0	0	5 x 3 x 2	3 x 2 x 6	2 x 6 x 1	6 x 1 x 4
   3	0	0	0	5 x 3 x 2 + 5 x 2 x 6 = 90	3 x 2 x 1 + 2 x 6 x 1 = 18	2 x 6 x 1 + 2 x 1 x 4 = 20
   4	0	0	0	0	??	??
   c1					5 x 3 x 1 + 3 x 2 x 1 + 2 x 6 x 1 = 33	??
   c2					5 x 3 x 2 + 5 x 2 x 1 + 2 x 6 x 1 = 52
   c3					5 x 3 x 2 + 5 x 2 x 6 + 5 x 6 x 1 = 120

   행렬을 1 : 3로 나누면 candidate1 = dp[0][1] + arr[0] x arr[1] x arr[4] +  dp[2][4]
   행렬을 2 : 2로 나누면 candidate2 = dp[1][2] + arr[0] x arr[2] x arr[4] + dp[1][4]
   행렬을 3 : 1로 나누면 candidate3 = dp[2][3] + arr[0] x arr[3] x arr[4] + dp[0][4]
   dp[3][4] = Math.min(candidate1, candidate2, candidate3) 이다.

위 과정을 통해 아래와 같은 점화식을 구할 수 있다.

점화식에 따라 메서드를 작성해보자.

static int minProcession(int[] p, int n) {
        int[][] dp = new int[n+1][n+1];

        for(int count = 2; count <= n; count++) { // 사용되는 행렬 개수
            for(int end = count; end <= n; end++) { // 마지막 행렬의 순번
                dp[count][end] = Integer.MAX_VALUE;

                for(int k = 1; k < count; k++) { // k : count - k 로 행렬을 나눔
                    int start = end - count + 1;
                    int candidate = dp[k][end-count+k] + dp[count - k][end] + p[start - 1] * p[end - count + k] * p[end];
                    dp[count][end] = Math.min(dp[count][end], candidate);
                }
            }
        }
        return dp[n][n];
    }

만일 이해가 되지 않는다면, 코드에 숫자를 한번 대입해보면 이해가 될 것이다.

전체코드:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[][] procession = new int[N+1][2];

        for (int i = 1; i <= N; i++) {
            procession[i][0] = sc.nextInt();
            procession[i][1] = sc.nextInt();
        }

        int[] p = new int[N+1];
        p[0] = procession[1][0];
        for (int i = 1; i <= N; i++) {
            p[i] = procession[i][1];
        }

        System.out.println(minProcession(p, N));
    }

    static int minProcession(int[] p, int n) {
        int[][] dp = new int[n+1][n+1];

        for(int count = 2; count <= n; count++) { // 사용되는 행렬 개수
            for(int end = count; end <= n; end++) { // 마지막 행렬의 순번
                dp[count][end] = Integer.MAX_VALUE;

                for(int k = 1; k < count; k++) { // k : count - k 로 행렬을 나눔
                    int start = end - count + 1;
                    int candidate = dp[k][end-count+k] + dp[count - k][end] + p[start - 1] * p[end - count + k] * p[end];
                    dp[count][end] = Math.min(dp[count][end], candidate);
                }
            }
        }
        return dp[n][n];
    }
}

 

시행착오:

오랜만에 행렬에 대한 개념 정리하는 것 자체는 기억도 새록새록 나고 나쁘지 않았다.
하지만, 점화식을 구하는것 자체가 너무나 복잡했다...

처음에는 다른사람의 풀이를 보고 적당하게 이해 했지만,
블로그를 작성하며, 문제를 정확하게 이해하고 설명해야 했고, 나만의 풀이법을 찾아야 했다.

풀이법을 찾은 이후에도 점화식에 맞춰 코드를 작성해야했는데, 이때가 상당히 복잡했다.

그렇게 고통받던 중에 내가 코드를 작성하며, 함수명과 주석을 너무 덜 이용하고 있다는 것이 느껴졌다.

 

함수명은 i, j, k 등 보편적인 이름 대신 count, start, end로 사용하니 훨씬 점화식과 코드를 연관짓기 쉬웠고, 주석까지 함께 이용하니 그때서야 코드를 정확하게 작성할 수 있었다.

 

만약 다른사람이 내 코드를 보고 이해해야하는 상황이라면 어떨까?
정확한 함수명과, 주석이 필수일 것이다. 앞으로도 주석과 함수명에 신경써서 코드를 작성하도록 하자.