글 읽기 - 어디가 틀린건지 모르겠습니다.

companyofpotato 3년 전 0

예제도 돌려보고, 게시판에 있는 반례도 다 돌려봤는데도 계속 제출하자마자 '틀렸습니다'가 나옵니다. 애초에 제 알고리즘이 틀린건지 다른 반례가 있는지 궁금합니다.

제가 생각한 알고리즘은,

주어진 정수들을 정렬한 다음에 정수가 하나만 주어지거나, 음수만, 양수만, 음수와 0 혹은 양수와 0이 주어지는 경우들을 먼저 고려한다음에,

음수 양수가 같이 주어지는 경우에(35번째 줄부터) 가장 작은 음수에 양수나 0이 될때까지 가장 큰 양수부터 더하고, 그 다음 음수에 양수들을 더하는 식입니다.

for문이 끝나면 양수만, 음수만, 양수와 0, 음수와 0 혹은 0만 남게 되는데 이걸 다시 정렬해서 합이 될 값의 부호를 판별합니다.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	for (int i = 0; i < 3; i++)
	{
		int t;
		std::cin >> t;
		std::vector<long long> v;
		long long n;
		for(int i = 0; i < t; i++)
		{
			scanf("%lld", &n);
			v.push_back(n);
		}
		std::sort(v.begin(), v.end());

		if (t == 1)
		{
			if (v[0] < 0)
				std::cout << "-";
			else if (v[0] > 0)
				std::cout << "+";
			else
				std::cout << "0";
		}
		else if (v[0] == 0 && v.back() == 0)
			std::cout << "0";
		else if (v[0] >= 0)
			std::cout << "+";
		else if (v.back() <= 0)
			std::cout << "-";
		else
		{
			for (int i = 0; i < t; i++)
			{
				if (v[i] < 0)
				{
					while (v.back() > 0 && v[i] < 0)
					{
						v[i] += v.back();
						v.pop_back();
						t--;
					}
				}
				if (i + 1 < t && v[i + 1] <= 0)
				{
					v[i + 1] += v[i];
					v[i] = 0;
				}
			}

			std::sort(v.begin(), v.end());

			if (v[0] == 0 && v.back() == 0)
				std::cout << "0";
			else if (v.back() <= 0)
				std::cout << "-";
			else if (v[0] >= 0)
				std::cout << "+";
		}

		puts("");
	}

	return 0;
}

sait2000 3년 전 1

반례 드립니다. 41번 줄 루프가 끝난다고 v[i]가 0 이상이 되는 건 아닙니다.

3
0
0
0
3
0
0
0
3
-9223372036854775807
-9223372036854775806
1

companyofpotato 3년 전 0

@sait2000

음수로 매우 큰 수가 연속으로 나오는 경우를 생각 못했네요...

v[i]가 0보다 크거나 같을 때만 v[i + 1]에 v[i]를 더하도록 if문을 추가해서 정답을 맞췄습니다. 갑사합니다!

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

문제

문제

출처

ICPC

어디가 틀린건지 모르겠습니다.

companyofpotato 3년 전 0

sait2000 3년 전 1

companyofpotato 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말