[백준/BOJ] 백준 코딩 알고리즘 11049번/C++

 백준 코딩 알고리즘 문제 11049번

 

백준 코딩 알고리즘 문제 11049번 풀이 - 사용 언어: C++

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int mArr[501][2] = { 0, }; // 행렬 정보를 저장
int dp[501][501] = { 0, }; // 행렬i부터 j까지의 최소연산횟수를 저장
 
int main() {
 
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> mArr[i][0]; //i번째 행렬의 행값
        cin >> mArr[i][1]; //i번째 행렬의 열값
        dp[i][i] = 0;
    }
 
    for (int term = 1; term < N; term++) { //간격
        for (int start = 1; start <= N - term; start++) {
            int end = start + term;
            int min = 987654321;
            for (int mid = start; mid < end; mid++) {
                int temp = dp[start][mid] + dp[mid+1][end] + mArr[start][0] * mArr[mid][1] * mArr[end][1];
                if (temp < min)
                    min = temp;
            }
            dp[start][end] = min;
        }
    }
 
    cout << dp[1][N] << endl;
 
    return 0;
 
}

참고 사이트: https://zzinnykim.tistory.com/31