백준 11049 - 행렬 곱셈 순서(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

DP 문제였습니다.

문제 조건

출력 예시

N개의 행렬을 합치는데 필요한 최소 연산 횟수를 구하는 문제였습니다.

위와 같이 행렬이 곱해질 때는, 행렬이 (m,k)인 행렬로 바뀌게 됩니다. 이때의 연산 횟수는  m * n * k가 됩니다.

 

이점을 유의하고 점화식을 접근해 보겠습니다.

(1 ~ N) 까지의 행렬을 연산 횟수는 많은 경우의 수가 있습니다. 그렇기에 모든 경우의 수를 확인할 수 없으니 (1 ~ K) + (K+1 ~ N)으로 나누어 두 그룹의 연산 횟수의 최솟값을 구한 뒤 더하는 방법으로 접근하겠습니다.

 

예를 들어, Dp[1][3] (1번부터 3번 행렬까지의 최소 연산 횟수)를 구하기 위해서는 

1. Dp[1][1] + Dp[2][3] + 1번 행렬과 (2,3) 행렬의 연산 횟수

2. Dp[1][2] + Dp[3][3] + (1,2) 행렬과 3번 행렬의 연산 횟수

위 2개의 경우로 나뉘어, 두 값중 최솟값이 Dp[1][3]의 값이 될 것입니다.

 

그렇다면 Dp[2][3]이나 Dp[1][2]의 값은 어떻게 구할 수 있을까 생각해보면

Dp[1][2] = Dp[1][1] + Dp[2][2] + 1번 행렬과 2번 행렬의 연산 횟수

Dp[2][3] = Dp[2][2] + Dp[3][3] + 2번 행렬과 3번 행렬의 연산 횟수

이때, Dp[1][1]과 같이 자기 자신을 연산하는 경우에는 0입니다. 

 

즉, Dp[i][j]일 때, i와 j의 차이가 1이라면, i번 행렬과 j번 행렬의 연산 횟수만이 최솟값으로서 저장이 됩니다. 

이렇게 i와 j의 차이가 1일 때부터 시작하여, N-1까지 차이를 계속 늘려가면 1 ~ N 행렬까지의 최소 연산 횟수를 구할 수 있습니다.

 

따라서 점화식은

Dp[dx][dy] = min(Dp[dx][dy], Dp[dx][mid] + Dp[mid+1][dy] + (dx, mid), (mid+1, dy) 행렬의 연산횟수) 

이때 (dx, mid)와 (mid+1, dy) 행렬의 연산 횟수는 (m,n) / (n,k) 일때 m * n * k의 값이 될 것입니다.

 

위의 설명을 출력 예시를 통해서 보여드리겠습니다.

 

문제 접근 방법

1. 행렬의 값을 받는다. 이때, 연산후의 행렬의 저장하는 배열에 [i][i]에 값을 같이 저장한다.

2. i와 j의 차이가 1일 때부터 N-1 때까지 배열을 반복한다.

3. 중간 값을 통해 두개의 그룹으로 나눈 뒤, 이때의 최솟값을 구한다.

4. Dp[1][N]의 값을 출력한다. 

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N;
pair<int, int> matrix[501];
int dp[501][501];
pair<int, int> dp_matrix[501][501];

int Sum(int dx, int mid, int dy) {
	return dp_matrix[dx][mid].first * dp_matrix[dx][mid].second * dp_matrix[mid + 1][dy].second;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> matrix[i].first >> matrix[i].second;
		dp_matrix[i][i] = matrix[i];
	}
	for (int i = 1; i < N; i++) {
		for (int dx = 1; dx + i <= N; dx++) {
			int dy = dx + i;
			dp[dx][dy] = 2147483647;
			for (int mid = dx; mid < dy; mid++) {
				dp[dx][dy] = min(dp[dx][dy], dp[dx][mid] + dp[mid + 1][dy] + Sum(dx, mid, dy));
			}
			dp_matrix[dx][dy].first = matrix[dx].first;
			dp_matrix[dx][dy].second = matrix[dy].second;
		}
	}
	cout << dp[1][N];
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!