[BOJ11049/Java] 행렬 곱셈 순

문제 요약

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

어렵다.. 행렬 곱셈도 이해하고 있고.. 순서에 따라서 필요한 연산 수가 달라진다는 것도 이해했으나..

이걸 어떻게 최소의 연산을 생각하는가.. 이해가 가지 않았다...

 

입/출력

다행스럽게도 문제에서 결합법칙만 신경쓰면 된다. 행렬의 순서를 다시 배치하지는 않아도 된다.

입출력이 크지 않다고 생각할 수 있으나 행렬의 개수가 500개이고 어떤걸 먼저 계산할건지 하나하나 다 해보면 499!의 경우의 수가 나오지 않나.. 절대 단순한 계산으로는 구할 수 없다.

 

접근 아이디어

그렇다면 계산을 어떻게 단순화할 수 있을까.. 생각을 계속해봐도 답이 안나와서

검색 찬스를 좀 썼다.. 근데 그래도 이해가 안간다..

일단 제일 중요하다고 생각한 부분은 어떤 부분을 제일 나중에 계산할까에 대해서 처리하는 부분인데

중복적인 계산이 계속 생기므로 dp를 풀이 방식으로 생각해야하고, bottom-up을 기준으로 해서 생각해보면

일단 gap을 2로 두면 0, 1, 2에 대해서 0*(1*2)와 (0*1)*2 중 어떤 것이 더 작은지 비교해야한다.

근데 (1, 2)*3 과 1*(2*3) 중 어떤 것이 더 작은지 비교할 때 (1*2)가 중복으로 계산방법이 구해진다.

그래서 미리 자기 바로 옆 행렬과의 값을 구해두는게 좋겠다. 그래서 dp[i][i+1]에는 바로 옆의 행렬과의 계산에 필요한 연산수를 저장한다. dp[i][i]는 자기자신과의 곱셈에는 연산이 필요없으므로 0을 넣는다.

그 다음으로는 이제 세 행렬을 곱하는 과정에서 최솟값을 구하려고 한다.

인덱스를 3개를 두고 이동해가면서 dp 배열을 채우는데

i, k, j 세 개에 대해서 i부터 j까지 곱하는데 필요한 연산의 최솟값을 dp[i][j]에 대입한다.

이 때 k는 i와 j-1 사이를 이동하면서 (i~k 까지 계산하는데 필요한 연산 수 dp[i][k])와 (k+1부터 j까지 계산하는데 필요한 연산수 dp[k][j]), 그리고 (i~k 행렬, k+1~j 행렬을 곱하는데 필요한 연산 수)를 계산해서 dp[i][j]에 들어갈 후보값을 만들고

이를 원래의 값과 비교해가면서 최솟값을 찾아 dp[i][j]를 업데이트 한다.

글을 쓰다보니까 이제 이해가 됐는데 작성 코드는 다음과 같다!

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

public class BOJ11049 {

	static int N;
	static int[] mat;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		mat = new int[N+1];
		StringTokenizer st;
		
		for(int i = 0; i< N; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			mat[i] = n;
			mat[i+1] = m;
		}
		
		int[][] dp = new int[N][N];
		for(int i = 0; i< N-1; i++) {
			dp[i][i+1] = mat[i] * mat[i+1] * mat[i+2];
		}
		
		for(int gap = 2; gap < N; gap++) {
			for(int i = 0; i + gap < N; i++) {
				int j = i+gap;
				dp[i][j] = Integer.MAX_VALUE;
				
				System.out.println(dp[i][i]);
				for(int k = i; k<j; k++) {
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + (mat[i]*mat[k+1]*mat[j+1]));
				}
			}
		}
		
		System.out.println(dp[0][N-1]);
	}

}