[백준] #11049 행렬 곱셈 순서 - (DP)

문제

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

11049번: 행렬 곱셈 순서

목표

행렬 연산을 할때 곱셈순서에 따라 값은 변하지 않지만 필요한 곱셈연산의 수는 달라진다.

따라서 주어진 행렬들이있을때 최소 곱셈 연산횟수를 구하라

 

풀이

ㅈㄴ어려움..

재귀로 푸는방법과 반복문으로 푸는방법이 있다.

1. 재귀

일단 재귀는 top-down으로 푸는데

점화식은

for (int i=left; i<right; ++i) {

   dp[left][right] = min(result, func(left, i) + func(i+!, right) + (arr[left].first * arr[i].second * arr[right].second) )

}

즉, left, right구간의 최소 연산횟수는 left와 right사이에 i라는 변수를 두어 (left~i)연산횟수 + (i+1~right)연산횟수 + 앞 두 연산의 결과인 행렬 두개의 연산횟수로 계산한후, i값에 따른 최소 연산횟수를 최종 dp[left][right]로 저장한다.

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX = 501;
const int INF = 987654321;
int N;
pair<int, int> arr[MAX];
int dp[MAX][MAX];

int func(int left, int right) {
    if (left == right)
        return 0;
    int result = dp[left][right];
    if (result != -1)
        return result;
    result = INF;
    for (int i=left; i<right; ++i) {
        result = min(result, func(left, i) + func(i+1, right) + 
                            arr[left].first*arr[i].second*arr[right].second);
    }
    return result;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for (int i=0; i<N; ++i) {
        cin >> arr[i].first >> arr[i].second;
    }
    memset(dp, -1, sizeof(dp));
    cout << func(0, N-1);
    return 0;
}

2. 반복

이해하는데 너무 힘들었고 아직도 이해했는지 잘 모름

일단 bottom-up으로 코딩

diff라는 변수로 1번 for루프를 돈다

     diff는 우리가 구하고자하는 행렬들 사이의 간격을 말한다. 즉 diff=1이면 1칸 떨어진 행렬들의 곱셈연산횟수를말함

     10개의 행렬이 주어진다면 최종적으로 구해야할 행렬의 간격이 9임

     예를 들어 diff=9 라면 최종적으로 dp[1][10]을 구하는거임

     따라서 diff=0이면 같은 행렬이므로 0번의 연산, diff=1이면 옆행렬과의 연산횟수, diff=5라면 5칸뒤의 행렬과의          연산 횟수를 말함

다음 start는 구할 행렬집합의 시작인덱스 end는 마지막인덱스 따라서 end = start + diff임

다음 mid는 구할 행렬집합의 연산횟수를 중간에 있는 행렬을 기준으로 나누는데 필요한 인덱스

코드

#include <iostream>
#define MAX 501

using namespace std;

int N;
int arr[MAX][2];
int dp[MAX][MAX];

//diff = 연산횟수를 구할 행렬의 간격
//start = 구할 행렬집합의 시작점
//end = 구할 행렬집합의 끝점
//mid = 구할 행렬집합의 연산 순서를 바꾼 값들을 비교하기위한 변수
int func() {
    for (int diff = 1; diff < N; ++diff) {
        for (int start=1; start<=N-diff; ++start) {
            int end = start + diff;
            int res = 987654321;
            for (int mid = start; mid<end; ++mid) {
                int tmp = dp[start][mid] + dp[mid+1][end] + 
                        arr[start][0]*arr[mid][1]*arr[end][1];
            if (res > tmp)
                res = tmp;
            }
            dp[start][end] = res;
        }
    }
    return dp[1][N];
}
int main() {
    cin >> N;
    for (int i=1; i<=N; ++i) {
        cin >> arr[i][0] >> arr[i][1];
    }

    cout << func();
}