백준 11066 C++

#include <bits/stdc++.h>

using namespace std;

int testCase;
int n;
int arr[510];
int sum[510];
int dp[510][510];

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

	cin >> testCase;

	while (testCase--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			//dp[i][i] = arr[i];
			sum[i] = sum[i - 1] + arr[i];		//누적합
		}

		for (int len = 1; len < n; len++) {
			for (int start = 1; start + len <= n; start++) {
				int end = start + len;
				dp[start][end] = INT_MAX;

				for (int mid = start; mid <= end; mid++) {
					int cost = dp[start][mid] + dp[mid + 1][end] + (sum[end] - sum[start-1]);
					dp[start][end] = min(dp[start][end], cost);
					
				}
				//cout << "start : " << start << "  end : " << end << "  " << dp[start][end] << "\n";
			}
		}
		cout << dp[1][n] << "\n";
	 }
}

처음엔 (dp[start][mid] + dp[mid+1][end] ) * 2라고 생각했는데

이건 전체의 합을 나타내야하는데 dp는 최소값을 나태낸 것이기에 달라서

Sum이라는 배열을 추가해서 빼주었다.