[백준 11049번/JAVA] 행렬곱셈순서 (문제 풀이, 코드)

행렬곱셈순서

[문제]

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

 

[풀이]

문제에 따르면,

N x M (A)

M x K (B)

=> N x M x K = mat[A][ROW] x mat[A][COL] x mat[B][COL]

을 알 수 있다.

첫 번째 행렬부터 마지막 행렬까지 곱셈 연산의 수의 최소값을 구해야한다.모든 경우를 다 따져보기엔 시간 초과가 날 게 분명하니, dp를 이용한다.

 

[내 코드 알고리즘]

dp는 복잡한 문제를 간단한 문제로 나눠 푸는 방식이다.

그럼 dp[1][N] 까지 구해야하는 복잡한 문제의 첫 발은 무엇일까?

(* 여기서 dp[A][B]는 A번째 행렬부터 B번째 행렬까지의 곱셈 연산의 수의 최소값이다.)

dp 배열을 초기화하는 것이다.

dp 배열에는 Math.min을 이용해야하기 때문에 배열은 큰 값으로 초기화 시켜준다.

dp[i][i] 와 같은, 자기 자신을 곱하는 것은 의미 없기 때문에 0을 넣어준다.

 

그 다음에는 구할 수 있는 값을 구한다.

dp[i][i+1]를 구해 넣어주면 된다.dp[i][i+1] = mat[i][R] * mat[i][C] * mat[i+1][C]를 다 구해넣어준다.

 

한 칸 짜리 행렬의 곱들을 다 넣어줬으면, 이제부터는 거리를 늘린다.

행렬 세 개의 곱의 최소값을 구하는 과정

dp[시작][시작+1]은 다 구했기 때문에, dp[시작][시작+2]를 처음부터 다 구해준다!

이때 +2를 전부 구해줘야하기 때문에 중첩 for문의 제일 위 조건이 길이(+2, len)이다.

그 다음 for문의 조건이 시작점이고 끝점은 시작점+len으로 구해줄 수 있다.

마지막 for문에는 중간점을 넣어준다.

이렇게 dp를 다 채워준 후 dp[1][N]을 출력하면 답. 

 

[코드]

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

public class Main {
	static int ROW =0;
	static int COL = 1;
	static int MAX = Integer.MAX_VALUE;
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 행렬의 개수
		int[][] mat = new int[N+1][2]; // 0:ROW, 1:COL
		for(int i=1;i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			mat[i][ROW] = Integer.parseInt(st.nextToken());
			mat[i][COL] =Integer.parseInt(st.nextToken());
		}
		long[][] dp = new long[N+1][N+1]; // i부터 j행렬까지의 곱의 최솟값
		for(int i=1; i<=N; i++)
			for(int j=1; j<=N; j++) {
				if(i==j) dp[i][j]=0;
				else dp[i][j]=MAX;
			}
		
		for(int i=1; i<N; i++)
			dp[i][i+1] = mat[i][ROW] * mat[i][COL] * mat[i+1][COL];
		
		for(int len=2; len<=N; len++) { // 행렬 곱셈할 길이
			for(int i=1; i<= N-len; i++) { // 시작
				int j = i+len; // 끝
				for(int k=i; k<j; k++) // 중간점
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + mat[i][ROW] * mat[k][COL] * mat[j][COL]);
			}
		}
		System.out.println(dp[1][N]);
	}
}

[어려운점]

dp문제는 가장 작은 문제를 찾고, 그 문제를 커지게 하는 게(점화식을 찾는 것) 역시 어려운 것 같다.

이번 문제 역시 혼자서 떠올리기 막막해서 구글 검색과 질문게시판을 참고했다.

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

https://github.com/MOBUMIN/BJalgorithm/blob/master/11000-11999/MultiMatrix_11409.java

MOBUMIN/BJalgorithm