백준 11049번 행렬 곱셈 순서

< 백준 11049번 행렬 곱셈 순서 - 마포 코딩박 >

사용한 알고리즘: DP


 N개의 행렬을 곱할 때, 곱셈 순서에 따라 총 연산수가 달라집니다. 가장 작은 총 연산수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 10~11)
 'dp[x][y]: x번째행렬 ~ y번째 행렬 을 곱할 때 최소 연산수' 라고 설정했습니다.

(2) (코드 29~31)
 행렬을 2개만 묶어서 곱해보면서 dp[i][i+1] 을 초기값으로 구했습니다.

(3) (코드 32~39)
 i~i+k 씩 묶어서 최소연산수(dp)를 구했습니다. k=2~N-1 (3개씩, 4개씩, ... , N개씩 묶어봤습니다.)

(4) (코드 13~19)
 i~i+k 묶음의 dp[i][i+k] 를 계산하는 함수를 만들었습니다.
 전체 i~i+k 구간을 두 구간으로 나누는 가능한 모든 경우를 생각합니다.
 즉 {i, (i+1)~(i+k)}, {i~i+1, (i+2)~(i+k)}, ... , {i~(i+k-1), i+k} 의 모든 경우를 봅니다.
 각각의 경우에서 연산수는 " 두 구간의 최소연산수 합 + 두 구간에서 나오는 행렬을 곱하는 연산수 " 입니다.
 두 구간으로 나누는 모든 경우의 연산수 중 가장 작은 값이 dp[i][i+k] 입니다.

(5) (코드 41)
 구하고자하는 답은 1번째 행렬~N번째 행렬 곱의 최소 연산수 = dp[1][N] 입니다.

	#include <iostream>
	#include <utility>
	using namespace std;
	typedef long long ll;
	typedef pair<int, int> pii;
	const int MAX = 500;
	const ll INF = 1110987654321LL;
	int N;
	// dp[i][j] : i번행렬 ~ j번행렬 을 곱하는 최소 연산수
	ll dp[MAX+1][MAX+1];
	pii arr[MAX+1];
	ll Mini(int a, int b){
	ll ret = INF;
	// k: a ~ a+k 이랑 a+k+1 ~ b 으로 2 구간으로 나누어 생각
	for(int k=0; k<b-a; ++k)
	ret = min(ret, dp[a][a+k]+dp[a+k+1][b]+arr[a].first*arr[a+k].second*arr[b].second);
	return ret;
	}
	int main(){ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for(int i=1; i<=N; ++i){
	int a, b;
	cin >> a >> b;
	arr[i] = pii(a,b);
	}
	// 초기값 : i~i+1 2개만 묶어 계산한거
	for(int i=1; i<N; ++i)
	dp[i][i+1] = arr[i].first*arr[i].second*arr[i+1].second;
	// i ~ i+k 까지 k개씩 묶어서 생각
	for(int k=2; k<N; ++k){
	for(int i=1; i<=N; ++i){
	// N 넘어가면 안됨
	if(i+k > N) break;
	dp[i][i+k] = Mini(i,i+k);
	}
	}
	cout << dp[1][N] << '\n';
	return 0;
	}

view raw BOJ 11049.cpp hosted with ❤ by GitHub