[C/C++] 백준 11049번 - 행렬 곱셈 순서 (DP)

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 1000000000

int N, r, c;
int sum[501], matrix[501][2], dp[501][501];

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> r >> c;
		matrix[i][0] = r;
		matrix[i][1] = c;
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = 1; i + j <= N; j++)
		{
			dp[j][i + j] = INF;
			for (int k = j; k <= i + j; k++)
			{
				dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i+j][1]);
			}
		}

	}

	cout << dp[1][N];


}

 

풀이 방법

cocoon1787.tistory.com/317

[C/C++] 백준 11066번 - 파일 합치기 (DP)

이번 문제도 11066번 파일 합치기 문제와 비슷한 문제입니다.

삼중 for문을 이용하여 시간 복잡도는 O(N³)이고 DP를 통해 풀이를 하였습니다.

dp[x][y] : x~y구간의 곱셈 연산 최솟값.

 

즉, dp[3][7]은 3번째 행렬부터 7번째 행렬까지 곱했을 때의 최소의 곱셈 연산 횟수를 의미합니다.

 

위의 예제입력 1로 풀이과정을 설명드리겠습니다. 

설명하기 앞서 먼저 위의 세 행렬을 곱하게 되면 최종적인 행렬의 모습은 어떠할까요?

 

 

최종적으로 5x6행렬이 만들어집니다. 즉 가운데에 어떠한 행렬이 있든(행렬의 순서는 곱셈을 할 수 있는 크기로 주어진다고 문제에 나와있습니다.) 가장 첫 번째 행렬의 행과 가장 마지막 행렬의 열의 크기의 행렬이 만들어지게 됩니다.

그렇다면 곱셈 연산의 횟수는 어떻게 나올까요?

 

문제에서 주어졌듯이 N x M x K로 구할 수 있습니다.

 

이제 코드를 살펴보자면, 

for (int i = 1; i < N; i++)
	{
		for (int j = 1; i + j <= N; j++)
		{
			dp[j][i + j] = INF;
			for (int k = j; k <= i + j; k++)
			{
				dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i+j][1]);
			}
		}

	}

삼중 for문으로 이루어져 있으며 가장 바깥쪽의 i는 구간 범위의 크기를 의미합니다. 즉 i가 만약 2라면 dp[1][3], dp[2][4], dp[3][5]........ dp[x][x+2]를 구한다는 얘기입니다. 

그리고 가운데 for문에서 j는 구간 범위의 시작지점을 의미합니다. dp[2][3], dp[2][6], dp[2][11]등등 모두 구간 범위의 시작 지점은 j = 2입니다.

그리고 가장 안쪽에 있는 for문에서 k는 구간 범위를 두 부분으로 나눌 때의 기준점입니다.

 

dp[j][i + j] = min(dp[j][i + j], dp[j][k]+dp[k + 1][i + j] + matrix[j][0]*matrix[k][1]*matrix[i+j][1]);

그리고 이번 문제풀이의 핵심인 for문 가장 안쪽의 dp를 구하는 코드를 보면 k를 기준으로 구간을 두 부분으로 나눕니다. 예를 들어 위의 그림을 활용해서 dp[3][7]을 구해야 할 때 dp[3][4]와 dp[4][7] 두 부분으로 나눕니다.

dp[3][4]로 N x M 크기의 행렬이 만들어지고 dp[4][7]로 M x K 크기의 행렬이 만들어지게 됩니다. 아까 위에서 봤듯이 두 행렬의 곱셈 연산 수는 N x M x K가 됩니다.

matrix[j][0]*matrix[k][1]*matrix[i+j][1]);

matrix[j][0] : 구간 시작 부분의 행렬의 행 (N 역할)

matrix[k][1] : 구간을 둘로 나누는 기준점 행렬의 열 (M 역할)

matrix[i+j][1] : 구간 마지막 부분의 행렬의 열 (K 역할)

따라서, 이 코드 부분은 구간을 두 부분으로 나눴을 때 그 두 부분의 행렬을 곱할 때의 연산 수를 의미하게 됩니다.

 

그리고 마지막으로 dp[1][N] (1~N번째의 행렬을 곱했을 때 연산의 최솟값)을 출력하면 정답입니다.

 

 

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서