187. 11049(행렬 곱셈 순서) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[][] rc = new int[N][2];
		int[][] dp = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			rc[i][0] = Integer.parseInt(tmp[0]);
			rc[i][1] = Integer.parseInt(tmp[1]);
		}

		for (int i = 1; i < N; i++) {
			for (int x = 0; x < N - i; x++) {
				int y = x + i;

				dp[x][y] = (int) Math.pow(2, 32);

				for (int k = x; k < y; k++) {
					dp[x][y] = Math.min(dp[x][y], dp[x][k] + dp[k + 1][y] + rc[x][0] * rc[k][1] * rc[y][1]);
				}
			}
		}
		
		System.out.println(dp[0][N-1]);
	}
}

문제요약

행렬의 곱셈 연산이 제일 적게 이행하는 최솟값을 구하라.

설명

행렬의 곱셈식은

이다.

따라서 연산 횟수는 x*z*y가 된다.

 

 

이 식을 기억하고 입력 예제를 보자.

다음과 같이 행렬의 크기가 주어지면

1. 5 * 3 * 2 + 5 * 2 * 6 = 30 + 60 = 90 

2. 3 * 2 * 6 + 5 * 3 * 6 = 36 + 90 = 126

으로 1번의 연산이 더 적다.

 

일단 DP 리스트에서 우리는 회색 대각선 기준 윗부분만 사용할 것이다.

계산은 각 색깔별로 진행된다.

DP[0][1] -> DP[1][2] -> DP[2][3] -> DP[3][4] -> DP[0][2] -> ... -> DP[0][4]

로 진행되며 DP[0][4] 가 출력값을 지니게 된다. 

 

		for (int i = 1; i < N; i++) {
			for (int x = 0; x < N - i; x++) {

 

먼저 i는 회색 대각선 하단 부분은 사용하지 않기 위해서 설정한 것이다.

따라서 x를 N-i만큼만 진행되도록 하였다. (다음 행이 될때마다 사용하는 주소가 줄어든다. 4 -> 3 -> 2 -> 1)

 

				int y = x + i;

y는 i + x로 설정하면 될것이다.

예를들어 

i가 1번째에서 x가 0 이면 arr[x][y] = arr[0][1] 이고, x가 1이면 arr[x][y] = arr[1][2] 이런식으로 진행된다.

 

				dp[x][y] = (int) Math.pow(2, 32);

				for (int k = x; k < y; k++) {
					dp[x][y] = Math.min(dp[x][y], dp[x][k] + dp[k + 1][y] + rc[x][0] * rc[k][1] * rc[y][1]);
				}
			}
		}

최소 값을 구하기 위해서 초반 셋팅값은 2의 32제곱으로 정해주었다.

연산횟수는 2의 31승 -1 보다 작거나 같기 때문에 최대한의 크기로 설정해 준것이다.

 

이제 본격적인 비교가 들어가는데 k를 x~y범위로 하여 계산을 진행한다.

 

아까 위에서 연산 횟수를 구할 때 식을 보면

[x][0] + ([x][1] 혹은 [y][0]) + [y][1] 인 것을 볼 수 있다.

즉, [x][0] + ?? + [y][1] 이라는 것을 알 수 있고, ??는 x 혹은 y가 들어가게 되어 k를 위와같이 설정해주었다.

 

 

DP[x][k] + DP[k+1][y]는 다음을 표시한것이다

빨간색 (현재)를 구하기 위해 노란색(DP[x][k] + DP[k+1][y]) 부분을 이용한 것이다.

 

 

결국 마지막 부분까지 하면 총 계산이 끝난 거고

x가 0 y가 끝부분을 가리 키는 빨간색 부분이 답이 된다.