[백준] 행렬 곱셈 순서 - 11049번

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
 
using std::vector;
 
typedef struct {
    int l;
    int r;
}objectpos;
int main(int argc, char* argv[]) {
    int n;
    int** dp;
    vector<objectpos> matrix;
 
    scanf("%d", &n);
    dp = new int* [n];
    for (int i = 0; i < n; i++) {
        int l, r;
        dp[i] = new int[n];
        memset(dp[i], 0, sizeof(int) * n);
        scanf("%d %d", &l, &r);
        matrix.push_back({l,r});
    }
 
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j+i+1 < n; j++) {
            int left = j, right = j + i+1;
            int temp;
            if (i == 0) {
                dp[left][right] = matrix[left].l * matrix[left].r * matrix[right].r;
            }
            else {
                dp[left][right] = dp[left + 1][right] + (matrix[left].l * matrix[right].r * matrix[left].r);
                for (int k = left + 2; k < right+1;k++) {
                    temp = dp[k][right] + dp[left][k - 1] + (matrix[left].l * matrix[right].r * matrix[k].l);
 
                    if (temp < dp[left][right])
                        dp[left][right] = temp;
                }
            }
        }
    }
    printf("%d", dp[0][n-1]);
 
 
    for (int i = 0; i < n; i++) {
        delete[] dp[i];
    }
    delete[] dp;
 
    return 0;
}

 

 

생각을 잘못해서 좀 걸렸다.