글 읽기 - 연속합 반례 좀 찾아주세요..

mareng825 4년 전 0

게시판에 있는 반례들 다 확인해봤는데 도저히 모르겠습니다...

dp[i]는 i번째 숫자까지의 연속합의 최대를 의미합니다.

tmp변수는 data[j]가 마이너스일 경우를 대비해 만들었습니다.

고수님들 도와주세요ㅠㅠㅠ

#include <iostream>
#include <algorithm>
using namespace std;

#define max_size 100001

int main() {

	int n, data[max_size], dp[max_size];
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> data[i];
	}
    
	dp[0] = data[1];

	for (int i = 1; i <= n; i++) {
		int sum = data[i];
		int tmp = 0;
		for (int j = i - 1; j >= 1; j--) {
			if (sum + data[j] < sum) {
				tmp += data[j];
			}
			else {
				if (sum <= sum + data[j] + tmp) {
					sum += data[j] + tmp;
					tmp = 0;
				}
				else break;
			}
		}
		dp[i] = max(dp[i - 1], sum);
		//cout << i << " " << dp[i] << endl;
	}

	cout << dp[n];
	return 0;
}

yomyom0824 4년 전 2

5
1000 2 1 -99 100
위 코드 실행값 : 1003

정답 : 1004

break; 문이 문제인 것으로 보입니다.

mareng825 4년 전 0

와 그렇군요 전혀 생각 못했습니다. 정말 감사합니다!!
혹시 이런 반례 찾는 요령같은 게 있을까요?

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

문제

문제

출처

ICPC

연속합 반례 좀 찾아주세요..

mareng825 4년 전 0

yomyom0824 4년 전 2

mareng825 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말