[C++] 백준 11049 행렬 곱셈 순서

 
#include <iostream>
#include <algorithm>
#include <vector>
 
int N = 0;
int r = 0;
int c = 0;
int sum[501] = {};
int matrix[501][2] = {};
int dp[501][501] = {};
 
int main()
{
	std::cin >> N;
 
	for (int i = 1; i <= N; i++)
	{
		std::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] = 2147483647;
 
			for (int z = j; z <= i + j; ++z)
			{
				dp[j][i + j] = std::min(dp[j][i + j], 
					dp[j][z] + dp[z + 1][i + j] + matrix[j][0] * matrix[z][1] * matrix[i + j][1]);
			}
		}
	}
 
	std::cout << dp[1][N];
 
	return 0;
}

 

 

순서대로는 항상 합할 수 있습니다.

그렇기 때문에 바로 행인지 열인지만 알면 계산이 가능합니다.

모든 것을 곱해야 하는 줄 알았지만 행과 열만큼만 횟수만 나오면 되기 때문에 계산한 것들을 더하면서 계산합니다.

j에서 i거리 사이 에 있는 dp는 j ~ i + j만큼 k로 돌면서 1, 2하고 3, 4해놓고 1,2,3,4 합치는 형식으로 계산합니다.

dp [1] [N]에 모두 합할 수 있습니다.