백준 11049 C++

와.. 어려웠다 이 문제

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

int n;
pair<int, int> arr[510];
int dp[510][510];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].first >> arr[i].second;
	}

	for (int len = 1; len < n; len++) {
		for (int start = 1; start + len <= n; start++) {
			int end = len + start;
			dp[start][end] = INT_MAX;
			for (int mid = start; mid < end; mid++) {
				int cost = dp[start][mid] + dp[mid + 1][end] + (arr[start].first * arr[mid].second * arr[end].second);
				dp[start][end] = min(dp[start][end], cost);
			}
		}
	}

	cout << dp[1][n] << "\n";
}

len으로 총 구할 범위를 정해주고

start로 구할 범위의 시작점을 정해준다.

그리고 end = len + start이니까 start 부터 len까지의 연산 횟수 최소값을 저장하는 dp가dp[start][end]이다.

mid는 어느 값이 최소인지 모르기에 start부터 end는 포함하지 않고 (mid+1을 하기에 end는 포함 X)

모든 구역을 돌면서 최소값을 구한다.