백준 11049(행렬 곱셈 순서)

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

11049번: 행렬 곱셈 순서

 

오랜만의 알고리즘

 

컨디션이 너무 안좋아져서..

 

아무튼 이 문제를 보면 대충 감이 안온다. 어떻게든 풀 수는 있을것 같은데..

처음에는 행값이 큰 거 순서대로 연산횟수를 줄이면 어떨까 싶었지만, 진행방법이 떠오르지 않아서 스킵하고, 스터디에서 진행하는 dp식으로 문제를 접근하였다. 

 

 

dp를 적용시키려면 문제의 부분 뭉텅이도 전체처럼 풀수 있을때 적용시키는 것 같다. 

 

뭔가 부분문제도 전체 문제처럼 반복된다고 생각이 든다면 정확할 필요없이, 그냥 대략적인 방법을 좀 더 구체화 해보자. 

 

이 문제도 처음에는 정교할 필요가 없다. 

 

ABCDE를 계산하는 방법을 생각해보면 된다. 

 

(AB)(CDE)이런식으로 전체 문제를 계산 가능하다. 

 

여기서 A(BCDE)

 

(BCDE)를 다시 전체 문제로 생각해서 계속해서 반복 계산하면 원하는 결과를 얻을 수 있을 것이라고 생각하기 쉽지 않을까 생각한다. 

 

그러면 이제 필요한건 점화식(코드)구현 

 

dp[i][j] := i,j까지 최소 연산 값을 저장하고 

 

dp[i][j] = min(dp[i][i+k] + dp[i+k+1][j] + a*b*c)를 k의 값으로 반복해서 그 중 가장 작은 dp[i][j]를 구한다. 

 

k가 의미하는건 

 

ABCDE에서 

 

어디를 가를것인가를 의미한다. 

 

k=1이면 (AB)(CDE)이런식으로 

 

 

여기서 for문을 돌릴때 주의할 점이 있다. 

 

단순 for(int i = ~){

         for(int j = i ~ ) 

 

로 돌리게 된다면 

 

dp[1][4]을 구하려고할때

 

위의 코드에서 비교해야 하는 dp[1][2] 는 구해져 있지만 dp[3][4]의 값은 구해져 있지 않은 상태기 때문에, 원하는 결과를 얻어 낼 수 없다. 따라서 길이가 1인 경우 2인경우 3인경우 순서대로 구한다. 

 

나머지 값들은 잘 설정해주면 된다.

#include<iostream>
#include<vector>
using namespace std;
#define MAX 501

vector<pair<int, int> > mat(MAX);
int dp[MAX][MAX];
int r, c, N;
int min_n = 987654321;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> r >> c;
		mat[i].first = r;
		mat[i].second = c;
	}
	for (int l = 1; l < N; l++) {
		for (int i = 1; i <= N-l; i++) {
			min_n = 987654321;
			int j = l + i;
			for (int k = 0; k < l; k++) {
				int temp = dp[i][i + k] + dp[i + k + 1][j] + mat[i].first*mat[i+k].second*mat[j].second;
				if (min_n > temp) {
					min_n = temp;
				}
			}
			dp[i][j] = min_n;
		}
	}
	cout << dp[1][N] << "\n";
}

 

 

dp문제는 특정한 알고리즘 방법이 아니다. 그냥 방법론? 이라고 해야할 것 같다. 

 

작은 문제의 해결방법과 큰 문제의 해결방법이 같다고 생각이 들면 그냥 대략적인 방법을 생각해보자 꼭 확실할 필요는 없는 것 같다. 

 

어차피 구체적으로 생각하기 시작하면서 문제되는 경우를 거르기 쉬우니깐