programmers 12942: 최적의 행렬 곱셈

행렬 N개가 있을 때 적절히 순서를 바꿔 곱을 할 경우 연산 횟수의 최소를 구하는 문제이다.

 

예를 들어 행렬 A(a,b), B(b,c), C(c,d)가 있을 때 곱하는 경우는 두 가지가 있을 수 있다.

• (AB)C 일 경우 연산 횟수 a*b*c + a*c*d = a*c*(b+d)
• A(BC) 일 경우 연산 횟수 b*c*d + a*b*d = b*d*(a+c)

 

행렬 곱을 구할 때, 이전에 구한 값을 재사용 할 가능성이 있기 때문에 dp로 문제를 푸는 방향으로 생각해 봤다.

dp[i][j]: i~j까지 행렬까지의 곱 중 가장 적은 연산 횟수라고 정의한다면,

i<=k<=j인 k에 대해 dp[i][k] + dp[k][j] + i*k*j 중 최소값이 dp[i][j]가 될 것이다.

class Solution {
	public int solution(int[][] matrix_sizes) {
		int length = matrix_sizes.length;

		Matrix matrix[] = new Matrix[length + 1];
		for (int i = 1; i <= length; i++) {
			matrix[i] = new Matrix(matrix_sizes[i - 1][0], matrix_sizes[i - 1][1]);
		}
		int dp[][] = new int[length + 1][length + 1];

		for (int i = length; i > 0; i--) {
			for (int j = i + 1; j <= length; j++) {
				dp[i][j] = Integer.MAX_VALUE;
				for (int k = i; k < j; k++) {
					dp[i][j] = Math.min(dp[i][j],
							dp[i][k] + dp[k + 1][j] + (matrix[i].row * matrix[k].col * matrix[j].col));
				}
			}
		}

		return dp[1][length];
	}
}

class Matrix {
	int row, col;

	public Matrix(int row, int col) {
		this.row = row;
		this.col = col;
	}
}