[BOJ-11049][DP] 행렬 곱셈 순서 - Java

문제 바로가기

11049번: 행렬 곱셈 순서

 

Chained Matrix Multiplication 문제입니다.

M[1, N]을 구해주면 되겠지용!

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

public class Main {
	static int N;
	static int[] d;			// 행열의 행, 열의 개수 (1번 행렬의 행의 수: d[0], 열의 수: d[1])
	
	public static void main(String[] args) throws Exception {
		input();
		System.out.println(solve());
	}
	
	public static int solve() {
		int[][] M = new int[N+1][N+1];

		for (int len = 1; len < N; len++) {		// len: i~j의 길이(j-i)
	        for (int i = 1; i <= N-len; i++) {
	            int j = i + len;
	            M[i][j] = Integer.MAX_VALUE;
	            
	            for (int k = i; k < j; k++) {
	                int cost = M[i][k] + M[k + 1][j] + d[i-1] * d[k] * d[j];
	                M[i][j] = Math.min(M[i][j], cost);
	            }
	        }
	    }
		
		return M[1][N];
	}

	public static void input() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		d = new int[N+1];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			d[i] = Integer.parseInt(st.nextToken());
			d[i+1] = Integer.parseInt(st.nextToken());
		}
	}
}

 

Chained Matrix Multiplication 에 대한 설명은 요기에 이씀다 ^_^

 

그럼 이 문제에서는 2차원 배열 M[][] 과 d를 구해주고 시작합니다. 

solve() 메소드에 있는 반복문을 봅시당. 우리는 M[i][j]를 쭉쭉 구해주면 되겠지용.

가장 바깥쪽 반복문에서의 len은 i~j의 거리입니다. 사실 거리-1 이긴 한데 대충 그렇다고합시다. j를 구할 때 i+len 으로 해주기 위함임니다. 그게 제 눈에 더 잘 보이걸랑요 ㅎㅎ

 

그다음은 i 입니다. 당연히 1부터 N-len 까지겠지용! i를 구하면 j도 바로 나옵니다. 그럼 여기 안에서 k를 구해가며 최솟값을 갱신하면 되겠지용. k는 응당 i부터 j-1까지가 되겠슴니다 허허.

 

최종 우리가 원하는 정답은 M[1][N] 에 들어있겠네용!

 

 

** 테케 하나 드림니다!! ** 

// 입력
6
5 2
2 3
3 4
4 6
6 7
7 8

// 출력
348

 

알고리즘 수업들을 때 기억이 새록새록 납디다.

심심할 때 괄호를 어떻게 쳐야하는지도 정리해보아야겠슴니다.

감사합니다!!