글 읽기 - 제발 한번만 봐주세요!!! 제발요 제발

smu04129 2년 전 0

점화식 아무리 봐도 어디를 잘못세웠는지 모르겠는데

두번째 테스트 케이스에서 970 이라는 엉뚱한 값이 나오네요..

저는 아무리 봐도 맞는것 같은데..

도움을 간절히 기다립니다.. 제발 도와 주세요.. 제발

#include <iostream>
#include <algorithm>
#define MAX 501
#define endl "\n"
using namespace std;

int t, n;
int sum[MAX], dp[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) { cin >> dp[i][i]; sum[i] = dp[i][i] + sum[i - 1]; }
		for (int i = 2; i <= n; i++) { dp[i - 1][i] = dp[i - 1][i - 1] + dp[i][i]; }
		for (int i = 3; i <= n; i++)
			for (int j = 1; j <= n - i + 1; j++) {
				dp[j][j + i - 1] = numeric_limits<int>::max();
				for (int k = j; k < j + i - 1; k++) {
					dp[j][j + i - 1] = min(dp[j][j + i - 1], dp[j][k] + dp[k + 1][j + i - 1] + sum[j + i - 1] - sum[j - 1]);
				}
			}
		cout << dp[1][n] << endl;
	}
}

kjyoa0009 2년 전 0

저도 970 나와서 확인해보니

저 같은 경우에는 2번 예제에서 3 4 5 에서 19가 아닌 24가 나오던데 한번 확인해보세요.

(7 + 5 + (3 + 4 + 5)) = 24

(7 + (3 + 4 +5)) = 19

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제발 한번만 봐주세요!!! 제발요 제발

smu04129 2년 전 0

kjyoa0009 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말