[알고리즘][BOJ]11049_행렬 곱셈 순서

BOJ_11049

💡 생각하자

[Dynamic Programming(동적 계획법)의 개발절차]
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기

재귀 관계식
A[i][j] : M(i)부터 M(j)까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수
A[i][j] = minimum(A[i][k] + A[k+1][j] + d(i-1)d(k)d(j)) (i <= k <= j-1)
A[i][i] = 0

💻 구현하자

• A[i][j]를 구하는 함수

int minMult() {
	// valid only when i<=j(upper triangle)

	for (int diagonal = 1;diagonal < n;diagonal++) {
		for (int i = 1;i <= n - diagonal;i++) {
			int j = i + diagonal;
			int min = INF;

			for (int k = i;k < j;k++) {
				int n_mul = A[i][k] + A[k + 1][j] + (d[i-1]*d[k]*d[j]);

				if (min > n_mul) {
					min = n_mul;
				}
			}

			A[i][j] = min;
		}
	}

	return A[1][n];
}

먼저, 위 그림과 같이 행렬에서 i<=j인 부분만 사용된다.

- 1번째 for문 : 대각선을 기준으로 진행되므로, 1번 대각선부터 n-1번 대각선까지 반복한다.
- 2번째 for문 : i는 1부터 n-diagonal, j는 i+diagonal이 된다.

그리고 각 k에 대해서, 행렬 곱셈에 필요한 곱셈 횟수를 구하여 최솟값을 갱신한다. 반복문 종료 후, A[i][j]에 저장한다.

• 초기 호출문

int res = minMult();

💥 발전하자

• 개선점

1. 대각선 방향으로 진행되는 점을 혼자서 알아내기 쉽지 않았다. 문제를 분석할 때 손으로 적어보면서 진행이 어떻게 되는지 파악하면 도움될 것 같다.

📌 참고하자

나의 코드(Github)