BOJ 11049 행렬 곱셈 순서

1 개요

BOJ 11049 행렬 곱셈 순서

• 백준 온라인 저지 11049번 문제
• BOJ 29단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, r[501], c[501];
int D[501][501];

int solve() {
    for(int i=0; i<N-1; i++){
        D[i][i+1] = r[i] * r[i+1] * c[i+1];
    }
    int start, end, pos, temp;
    for(int i=2; i<N ; i++){
        for(start=0; start < N-i; start++){
            end = start + i;
            for(pos=start; pos<end; pos++){
                temp = D[start][pos] + D[pos+1][end] + r[start] * c[pos] * c[end];
                if( D[start][end] == 0 || D[start][end] > temp )
                    D[start][end] = temp;
            }
        }
    }
    return D[0][N-1];  
}

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

    cin >> N;
    for(int i=0; i<N; i++){
        cin >> r[i] >> c[i];
    }
    cout << solve();
}