[Programmers] 최적의 행렬 곱셈

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12942

코딩테스트 연습 - 최적의 행렬 곱셈

DP를 이용하면 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. cache[i][j]: [i, j] 구간 내 행렬 최소 곱셈 연산 수를 저

2. 구간을 쪼개가며 현재 cache[i][j]와 비교하며 더 작은 연산 값을 저장

3. 2번을 진행한 후 cache[0][matrix_sizes - 1] 값을 반환

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	#include <set>
	#include <cstring>
	#include <climits>
	using namespace std;
	const int MAX = 200 + 20;
	int cache[MAX][MAX];
	int func(int start, int end, vector<vector<int>> &matrix_sizes)
	{
	if (start == end)
	{
	return 0;
	}
	int &result = cache[start][end];
	if (result != -1)
	{
	return result;
	}
	result = INT_MAX;
	for (int i = start; i < end; i++)
	{
	int calcCost = matrix_sizes[start][0] * matrix_sizes[i][1] * matrix_sizes[end][1];
	result = min(result, func(start, i, matrix_sizes) + func(i + 1, end, matrix_sizes) + calcCost);
	}
	return result;
	}
	int solution(vector<vector<int>> matrix_sizes) {
	memset(cache, -1, sizeof(cache));
	return func(0, matrix_sizes.size() - 1, matrix_sizes);
	}
	int main(void)
	{
	vector<vector<int>> matrix_sizes = {
	{ 5, 3 },
	{ 3, 10 },
	{ 10, 6 }
	};
	cout << solution(matrix_sizes) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~