백준 11049번 _ 행렬 곱셈 순서

2020-05-04 · 배운 것 · 3분 읽기

https://www.acmicpc.net/problem/11049

주의사항

1. 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다.
2. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

풀이방법

https://blog.fxjodo.com/blog/101/

이 문제와 거의 동일한 문제다. 다른 점이 있다면 점화식이
dp[start][end] = dp[start][mid] + dp[mid+1][end] + (start의 첫번째 * mid의 두번째 * end의 두번째) 이렇게 뒷부분이 이 문제에 맞게 조금 다르다는 점 정도다.

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

long long dp[501][501];
vector<pair<int, int>> matrix;
int n;

void Input()
{
	cin >> n;
	int start, end;
	for (int i = 0; i < n; i++)
	{
		cin >> start >> end;
		matrix.push_back({ start, end });
	}
}

void solve()
{
	for (int gap = 1; gap < n; gap++)
	{
		for (int start = 0; start+gap < n; start++)
		{
			int end = start + gap;
			dp[start][end] = LLONG_MAX;

			for (int mid = start; mid < end; mid++)
			{
				dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end]+ (matrix[start].first * matrix[mid].second * matrix[end].second));
			}
		}
	}
	cout << dp[0][n - 1] << endl;
}

int main()
{
	Input();
	solve();
	return 0;
}

후기

어제 고민해서 푼 문제와 거의 동일한 문제라 풀기 수월했다.