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

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

11049번: 행렬 곱셈 순서

풀이

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

11066번: 파일 합치기

개인적으로 11066번: 파일 합치기와 비슷한 문제라 느꼈습니다.

 

3

5 3

3 2

2 6

 

예제로 예시를 들어보겠습니다.

 

DP[start][end]를 start부터 end까지 행렬 곱셈 하는데 드는 연산의 수라고 가정하고

 

Matrix[i].y와 Matrix[i].x를 각각 해당 행렬의 행과 열이라 가정해봅시다.

 

분할정복 시 사용된 기준 값을 mid라는 변수로 명명했다고 할 시,

 

DP[1][3]은 min(DP[1][1] + DP[2][3], DP[1][2] + DP[3][3]) + Matrix[start].y * Matrix[mid].x * Matrix[end].x

 

로 나타낼 수 있습니다.

 

 

DP[1][1]은 0입니다.

 

DP[2][3]은 3 * 2 * 6으로 36입니다.

 

DP[1][1] + DP[2][3]은 그럼 36이고 이때 5 3 행렬과 3 6 행렬을 다시 곱해주어야 하는데,

 

3 6행렬은 2번째 행렬과 3번째 행렬이 곱해져서 만들어진 행렬입니다.

 

여기서 mid 값은 1이기 때문에

 

DP[1][1] + DP[2][3] + Matrix[1].y * Matrix[1].x * Matrix[3].x 가 됩니다.

 

풀어보면 0 + 36 + 5 * 3 * 6 = 126이 됩니다.

 

 

mid 값을 2로 옮기고

 

DP[1][2] + DP[3][3]의 경우를 보겠습니다.

 

DP[1][2]는 5 * 3 * 2로 30입니다.

 

DP[3][3]은 0이죠.

 

Matrix[1].y * Matrix[2].x * Matrix[3].x는 5 * 2 * 6으로 60입니다.

 

총연산 수는 30 + 60으로 90이 나오고 126보다 작기 때문에 답은 90입니다.

 

#include <iostream>
#include <limits>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 501;

pair<int, int> m[MAX];
int cache[MAX][MAX];

int DP(int start, int end)
{
    // 연산의 수 0 (하나의 행렬을 곱할 수 없음)
    if (start == end) {
        return cache[start][end] = 0;
    }
    
    // 캐시 반환 (이미 최솟값이 갱신된 경우)
    if (cache[start][end] != INF) {
        return cache[start][end];
    }
    
    // 분할정복
    for (int mid = start; mid < end; mid++) {
        int left = DP(start, mid);
        int right = DP(mid + 1, end);
        int temp = left + right + m[start].first * m[mid].second * m[end].second;
        cache[start][end] = min(cache[start][end], temp);
    }

    return cache[start][end];
}

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

    memset(cache, 0x3f, sizeof(cache));
    for (int i = 1; i <= n; i++) {
        cin >> m[i].first >> m[i].second;
    }

    cout << DP(1, n);

    return 0;
}

 

 

반례

Input

5
10 5
5 7
7 9
9 1
1 12

Output

268