[백준 11049] 행렬 곱셈 순서

DP를 활용하는 문제이다. 

 

DP 문제인건 보자 마자 알겠는데 어떻게 식을 세워야 할지 몰라서 찾아보다가 아래 유튜브 영상을 보고 이해를 했다.

https://youtu.be/prx1psByp7U

 

---

 

Bottom Up 방식으로 작은 부분먼저 계산해두고 최종 결과를 계산 해 나간다.

 

예를 들어 A,B,C 세개의 행렬의 곱셈 연산수를 구하기 위해서는 

(AB)C, A(BC) 의 연산 결과를 비교해야 한다.

이 때 괄호 안의 값인 AB, BC를 먼저 계산해서 dp배열에 저장 해 두고 최종 결과를 계산할 때 해당 값을 사용한다.

 

위 영상의 예제는 행렬 네개를 사용하여 설명하므로 A,B,C,D 네개의 행렬을 곱하는 예시를 들어보면 다음과 같다.

 

가장 처음엔 인접한 두개의 행렬들의 곱셈 연산 횟수를 계산한다.

문제에서 주어진 행렬들의 순서를 바꾸면 안되므로 인접한 두개의 행렬들만 곱한다.

 

다음엔 세개의 행렬을 곱한 결과를 저장한다.

 

네개의 행렬을 곱한 결과를 계산한다.

이 때 괄호 안의 값(ABC,BCD)는 당연 그 순서대로 곱한것이 아니고 이미 최소값을 찾아서 저장해둔 값을 사용한다.

최종 계산에 필요한 값을 계산하기 위해서는 작은 단위로 쪼개진 값의 결과가 필요한데 이 결과는 Bottom-up으로 올라오면서 다 계산되어 저장 해 둔 값이다.

 

 

이렇게 최종적으로 A,B,C,D 행렬을 곱할 때 최소 연산의 수를 구할 수 있다.

 

 

---

구현을 하기 위해서 각 배열의 행,열 값을 다음과 같이 일차원 배열 p에 저장해둔다.

행렬 A,B를 곱할때 연산 횟수는 5*4*6 이므로 P[0]*P[1]*P[2] 의 결과이다.

이처럼 P배열을 통해 인접한 행렬의 곱셈 연산수를 구할 수 있다.

 

연산 값을 저장해 둘 배열을 생성해서 연산값을 저장하는 단계는 다음과 같다.

점화식

m[i][j] = min(m[i][1] + [2][j]+ c1 , m[i][2]+[3][4]+ c2 , ... , m[i][k] + m[k+1][j] + c3)

c :  두개의 행렬을 곱하는 횟수 

 

항상 인접한 두개의 행렬을 곱하는데, 최적의 해를 찾기 위해서 어떻게 두개로 나누느냐를 고른다고 생각하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_11049_행렬곱셈순서 {

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

		int N = Integer.parseInt(br.readLine());

		int[] p = new int[N + 1];
		int[][] m = new int[N + 1][N + 1];

		int INF = Integer.MAX_VALUE;

		String[] s = br.readLine().split(" ");
		p[0] = Integer.parseInt(s[0]);
		p[1] = Integer.parseInt(s[1]);

		for (int i = 1; i < N; i++) {
			s = br.readLine().split(" ");
			p[i + 1] = Integer.parseInt(s[1]);
		}

		for (int d = 1; d <= N-1; d++) {
			for (int i = 1; i <= N - d; i++) {
				int j = i + d;
				m[i][j] = INF;
				for (int k = i; k <= j - 1; k++) {
					m[i][j] = Math.min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
				}

			}

		}
		System.out.println(m[1][N]);


	}

}