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

 

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

 

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

11049번: 행렬 곱셈 순서

---

 

 

해결전략

 

동적계획법 Dynamic Programming DP

 

 

---

 

정답코드

 

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

int n;
vector<pair<int, int>> v;
vector<vector<int>> dp;

int Cal(int start, int end) // start에서 end까지의 행렬 곱의 최소 연산 수를 계산
{
	if(start == end){ // 하나의 행렬만 있을 경우 곱셈 연산이 필요 없으므로 0을 반환
		return 0;
	}

	if(dp[start][end] != INT_MAX){  // 메모이제이션. dp 테이블에 계산된 값이 있으면 그 값을 반환하여 중복 계산을 피한다.
		return dp[start][end];
	}

	// start부터 end까지의 최소 곱셈 연산 횟수를 계산
	for (int k = start; k < end; k++) 
	{
		int count = Cal(start, k) + v[start].first * v[k].second * v[end].second + Cal(k + 1, end);

		dp[start][end] = min(dp[start][end], count);
	}

	return dp[start][end]; // 계산된 최소 비용을 반환
}

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

	cin >> n;
	v.resize(n);
	dp.resize(n, vector<int>(n, INT_MAX));
	for(int i = 0; i < n; i++){
		cin >> v[i].first >> v[i].second;
	}

	cout << Cal(0, n - 1) << "\n";

	return 0;
}

 

 

---

다른 풀이

 

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> matrix(n);
    for (int i = 0; i < n; i++) {
        cin >> matrix[i].first >> matrix[i].second;
    }

    // dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는데 필요한 최소 연산 횟수를 저장
    vector<vector<int>> dp(n, vector<int>(n, 0));

   
    for (int l = 2; l <= n; l++) {  // l은 행렬 곱셈을 계산할 행렬의 개수를 의미
        for (int i = 0; i <= n - l; i++) {
            int j = i + l - 1; // 현재 계산할 행렬 곱셈의 마지막 행렬 인덱스
            dp[i][j] = INT_MAX;

            // k를 기준으로 행렬을 두 부분으로 나누어 각 부분의 곱셈 연산 횟수의 합을 계산
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + matrix[i].first * matrix[k].second * matrix[j].second;
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}

 

 

 

---

 

 

다른 사람이 푼 더 나은 방식의 풀이

 

https://cocoon1787.tistory.com/318

 

https://junseok.tistory.com/103

 

---