글 읽기 - 질문드립니다.

orange4glace 8년 전 0

부분합을 이용하여 풀었습니다.

sum[i] 에는 0부터 i번째 까지의 부분합을 담았고

submin[i] 에는 sum 배열의 i 이하 원소중 최소값을 담아서

최종적으로 모든 i에 대해 sum[i] - submin[i - 1] 의 최대값을 출력하도록 했습니다.

여러가지 케이스를 테스트 해봤는데 다 정상적으로 나와서, 어떤 케이스가 틀린 것인지 궁금합니다.

#include "stdafx.h"
#include <stdio.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iostream>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)

int Q, N, M;
int sum[100001];
int submin[100001];

int main() {
	cout.sync_with_stdio(false);
	srand(time(NULL));

	cin >> N;
	int a;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &a);
		sum[i] = sum[i - 1] + a;
		if (submin[i - 1] > sum[i]) submin[i] = sum[i];
		else submin[i] = submin[i - 1];
	}
	int res = -INT_MAX;
	for (int i = 1; i <= N; i++)
		res = MAX(sum[i] - submin[i - 1], res);
	cout << res;

    return 0;
}

indioindio 8년 전 1

정수범위의 최소값은 -INT_MAX가 아니라 -INT_MAX -1 인데 입력으로

-2147483648

같은게 들어오는지는 잘 모르겠네요.

res를 어떤 경계값으로 잡기보다는 첫번째 원소같은 걸로 해두고 푸는 것을 추천드립니다.

indioindio 8년 전 2

위에 든 예시는 틀리도록 제출해봤더니 틀리네요(ㅠㅠ)

저런 입력이 존재하는 것 같습니다.

orange4glace 8년 전 0

답변 감사합니다.

말씀대로 고쳐봤는데.. 혹시 몰라서 자료형도 long long으로 했는데,

그래도 오답이 나네요.

혹시나해서 알고리즘이 틀려서 오답이 있는가 싶어서, 정답 코드와 제 코드를 가지고 랜덤 데이터를 무작위로 돌려봤는데, 모두 일치하더라구요..

ㅠㅠ 뭐가 문제인걸까요

int Q, N, M;
long long sum[100001];
long long submin[100001];

int main() {
	cout.sync_with_stdio(false);
	srand(time(NULL));

	cin >> N;
	int a;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &a);
		sum[i] = sum[i - 1] + a;
		if (submin[i - 1] > sum[i]) submin[i] = sum[i];
		else submin[i] = submin[i - 1];
	}
	int res = sum[1] - submin[0];
	for (int i = 1; i <= N; i++)
		res = MAX(sum[i] - submin[i - 1], res);
	cout << res;
	return 0;
}

100
-2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648 -2147483648

더하다가 자료형의 문제로 합의 값이 양수가 되어버려서 양의 값을 출력하는 것 같네요.

indioindio 8년 전 1

위의 저런 입력이 들어 지는 모르겠지만 합의 값이 음수라면 더 이상 고려하지 않거나 하는 (음수까지의 합 다음에 어떤 양수가 나온다면 그 수 하나만 취하는 게 이득이겠죠) 등의 방법을 추가하셔야 할 것 같습니다.

orange4glace 8년 전 0

답변 감사합니다. 많은 도움이 되었습니다

결국 다른 방법으로 풀 수 밖에 없나보네요..

indioindio 8년 전 1

네 조금 아쉽네요 정수자료형의 크기에 제한이 없는 언어라면 맞추셨을텐데요.

indioindio 8년 전 1

음 그리고 보니깐 알고리즘 자체에도 약간 문제가 있는 것 같습니다.

4000개의 양수로만 이루어진 랜덤입력에 대해서 오답을 출력하네요.

indioindio 8년 전 1

오... 잠시만요...

indioindio 8년 전 2

http://www.cplusplus.com/reference/ios/ios_base/sy...

에 의하면

With stdio synchronization turned off, iostream standard stream objects may operate independently of the standard C streams (although they are not required to), and mixing operations may result in unexpectedly interleaved characters.

라고 되어있네요. cout.sync_with_stdio(false); 를 켜고 cin, cout만 사용하거나 저 부분 없이 scan/ printf만 사용하셔야 할 것 같습니다.

랜덤생성으로는 입력부분을 거치지 않아서 발견할수가 없었던 모양입니다...ㅠ

indioindio 8년 전 1

확인 차 제출 해봤는데 양해 부탁드립니다.

orange4glace 8년 전 1

와 대박.....

진짜 감사드립니다!!!

너무 열심히 도와주셔서 ㅜㅜ 덕분에 정답이라는 문구를 볼 수 있었습니다

감사합니다!!

indioindio 8년 전 0

별 말씀을요 저도 덕분에 하나 배워가네요 :)

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

문제

문제

출처

ICPC

질문드립니다.

orange4glace 8년 전 0

indioindio 8년 전 1

indioindio 8년 전 2

orange4glace 8년 전 0

indioindio 8년 전 1

indioindio 8년 전 1

orange4glace 8년 전 0

indioindio 8년 전 1

indioindio 8년 전 1

indioindio 8년 전 1

indioindio 8년 전 2

indioindio 8년 전 1

orange4glace 8년 전 1

indioindio 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말