글 읽기 - 55%에서 7번가량 틀렸습니다..ㅠㅠ 반례 하나 들어주시면 감사하겠습니다.

legendmic2 3년 전 0

DP를 이용하여,

dl[i] : a[1] ~ a[i]에서의 최대합

dr[i] : a[i] ~ a[n]에서의 최대합

을 구하고

maxSum = INT_MIN 으로 초기화 한 후

maxSum = max(maxSum, dl[i-1] + dr[i+1]); 의 식을 통해 구하는 코드입니다.

질문게시판의 반례들은 다음과 같았습니다.

- 입력값이 1개일때의 오류 : if(n==1)로 구분하여 출력하도록 했습니다.

- 배열 사이즈가 넉넉치 못해서 틀렸을 가능성 : 상수 MAX를 100050으로 넉넉히 두었습니다.

- maxSum(다른 질문글들에선 res, sum, max 등)을 0으로 초기화하여 생긴 문제 : INT_MIN으로 초기화하였습니다.

반례들을 확인해도 어디에서 문제가 생기는지 모르겠어서 이렇게 질문드립니다.

끝까지 읽어주셔서 감사합니다.

#include <iostream>
#include <algorithm>
#include <climits>

#define MAX 100050

using namespace std;

int a[MAX + 1];
int dl[MAX + 1]; // dl[i] : a[1] ~ a[i]에서의 최대합
int dr[MAX + 1]; // dr[i] : a[i] ~ a[n]에서의 최대합

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

	int n; cin >> n;
	int maxSum = INT_MIN; // 최종 결과값

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

	if (n == 1)
	{
		cout << a[n] << "\n";
	}

	else
	{
		for (int i = 1; i <= n; ++i)
		{
			dl[i] = max(a[i], dl[i - 1] + a[i]);
		}
		// dl 완성

		for (int i = n; i >= 1; --i)
		{
			dr[i] = max(a[i], dr[i + 1] + a[i]);
		}
		// dr 완성

		maxSum = dl[n]; // 수열에서 수를 하나도 제거하지 않은 경우의 최대합

		for (int i = 1; i <= n; ++i)
		{
			maxSum = max(maxSum, dl[i - 1] + dr[i + 1]);
		}

		cout << maxSum << "\n";
	}
}

ha_ram 3년 전 2

반례입니다.

3
-1 -4 -3

답 : -1

legendmic2 3년 전 1

@ha_ram

감사합니다ㅠㅠ dl[n]이 가장 큰 값을 갖고 있을거라고 착각해버렸네요...

덕분에 풀었습니다! 감사합니다!

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

문제

문제

출처

ICPC

55%에서 7번가량 틀렸습니다..ㅠㅠ 반례 하나 들어주시면 감사하겠습니다.

legendmic2 3년 전 0

ha_ram 3년 전 2

legendmic2 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말