글 읽기 - 질문드리겠습니다..ㅠ

joonamin44 3년 전 0

58% 쯤에서 틀렸습니다. 라고 나와서 게시판에 있는 여러가지 반례들을 시도해봤지만

문제가 될만한 점들을 찾지를 못했습니다.. ㅠ 분할정복으로 시도했으며, 어디서 문제가 된 것인지 알려주시면 감사드리겠습니다.

#define MIN_VAL -987654321
#include <iostream>
using namespace std;
int arr[100000];
int solve(int start, int end){
	if( start >= end )
		return arr[start];
	
	int mid = (start+end)/2;
	
    // 수열이 중간값에 걸쳐 있을때, 즉 i <= mid <= j (i와 j는 최대합이 되는 구간의 시작과 끝 인덱스)
	int left = MIN_VAL;
	int sum = 0;
	for(int i=mid; i>=start ; i--){
		sum += arr[i];
		if( left < sum )
			left = sum;
	} 
	sum = 0;
	int right = MIN_VAL;
	
	for(int i=mid+1; i<=end ; i++){
		sum += arr[i];
		if( right < sum )
			right = sum;
	}
	
	int max = left+right;
	int left_side = solve(start,mid-1);
	int right_side = solve(mid+1, end);
	
	if( max < left_side ) max = left_side;
	if( max < right_side ) max = right_side;
	return max;
}
int main(void){
	int n;
	cin >> n;
	
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	int res = solve(0, n-1);
	cout << res;
	return 0;
}

djm03178 3년 전 1

반례입니다.

https://ideone.com/w1YEmW

joonamin44 3년 전 0

감사합니다!! 제가 right 부분에서 무조건 한개이상 원소를 택하도록 만들었군요 ㅜㅜ!

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

문제

문제

출처

ICPC

질문드리겠습니다..ㅠ

joonamin44 3년 전 0

djm03178 3년 전 1

joonamin44 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말