[BOJ 백준] 행렬 곱셈 순서 (11049) Java

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

 

문제 설명 : 

크기가 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(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

 

출력 : 

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

 

예제 입력 : 

3

5 3

3 2

2 6

 

예제 출력 : 

90

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

문제에서 강조되어 있는 부분을 보면서 분할정복이 떠올랐다.

ABCDEFGHIJ .... 수많은 행렬이 있을때, 

결국 문제를 해결하는 키는 가장 작은 상태로 쪼개서 확인하는 것이다.

 

분할정복 형태로 1개의 행렬까지 쪼갠 후 DP[ i ] [ j ] 는 i~j까지 행렬 곱의 최솟값으로 정의해서

아래 함수를 재귀로 호출하면 된다.

static int divideConquer(int start, int end) {
		// 자기 자신일때는 0 리턴
		if (start == end)
			return 0;

		// 갱신된적 있으면 다시 하지 않음
		if (dp[start][end] != Integer.MAX_VALUE) {
			return dp[start][end];
		}
		int left, right;
		for (int i = start; i < end; i++) {
			left = divideConquer(start, i);
			right = divideConquer(i + 1, end);
			dp[start][end] = Math.min(dp[start][end],
					left + right + (input[start].row * input[i].column * input[end].column));
		}
		return dp[start][end];
	}

 

전체 코드는 아래 참고.

 

2) 시간복잡도

최악의 경우 N^3 예상되나, N이 200으로 작아 무리 없음

(Java 기준 -  416ms)

 

3) 공간복잡도

N(500)이 크지 않아 고려하지 않음

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법

 

Java 코드 : 

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

public class Main {

	static class info {
		int row, column;

		public info(int row, int column) {
			this.row = row;
			this.column = column;
		}
	}

	static int N;
	static int[][] dp;
	static info[] input;

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

		// 1. 입력 받기
		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1][N + 1];
		input = new info[N + 1];

		StringTokenizer st;
		int r, c;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			input[i] = new info(r, c);
			for (int j = 1; j <= N; j++) {
				dp[i][j] = Integer.MAX_VALUE;
			}
		}

		divideConquer(1, N);

		bw.write(String.valueOf(dp[1][N]));

		bw.flush();
		bw.close();
		br.close();
	}

	static int divideConquer(int start, int end) {
		// 자기 자신일때는 0 리턴
		if (start == end)
			return 0;

		// 갱신된적 있으면 다시 하지 않음
		if (dp[start][end] != Integer.MAX_VALUE) {
			return dp[start][end];
		}
		int left, right;
		for (int i = start; i < end; i++) {
			left = divideConquer(start, i);
			right = divideConquer(i + 1, end);
			dp[start][end] = Math.min(dp[start][end],
					left + right + (input[start].row * input[i].column * input[end].column));
		}
		return dp[start][end];
	}
}