[백준][C++] 1247: 부호

문제 링크: https://www.acmicpc.net/problem/1247

 

변수 한개의 범위가 long long의 범위 \( \left [ -2^{64}, 2^{64}-1 \right ] \) 와 비슷한 \( \left [ -(2^{64}-1), 2^{64}-1 \right ] \) 입니다.

자바는 BigInteger를 써서 그냥 풀면 됩니다.

C++로 풀려면 다른 방법을 생각해 봐야겠죠. 이 문제를 푸는 방법이 여러 방법이 있겠지만 오버플로우를 카운트하는 방식으로 풀면 쉽습니다.

 

먼저 signed long long의 최소, 최대값은 LLONG_MAX, LLONG_MIN로 <climits>헤더에 정의되어 있습니다.

overflow 변수를 만들어서 0으로 선언하고, sum 변수를 하나 만들어서 여기에 값을 계속 더하는데 오버플로우가 발생한 경우 max값을 초과한 오버플로우면 ++overflow, min값 밑으로 넘어간 오버플로우는 --overflow를 해줍니다. (언더플로우가 아닙니다)

오버플로우인지는 아래처럼 판별하면 됩니다

• x+y > max이므로 x > max-y
  왼쪽 식을 그대로 쓰면 오버플로우가 나니까 식을 약간 변형합니다
• x+y < min이므로 x < min-y

 

수를 전부 입력받은 다음 overflow와 sum 변수를 비교해 값을 출력합니다.

• overflow == 0
  • sum == 0 : 0
  • sum > 0: +
  • sum < 0: -
• overflow > 0: +
• overflow < 0: -

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

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

	
	for (int tc = 1; tc <= 3; ++tc) {
		int overflow = 0;
		ll sum = 0;

		int n;
		cin >> n;

		ll in;
		while (n--) {
			cin >> in;
			if (sum > 0 && in > 0 && sum > LLONG_MAX - in) {
				//x + y > max  -->  x > max-y
				++overflow;
				sum += in;
			}
			else if (sum < 0 && in < 0 && sum < LLONG_MIN - in) {
				// x + y < min  -->  x < min - y
				--overflow;
				sum += in;
			}
			else {
				sum += in;
			}
		}

		if (overflow > 0)
			cout << "+";
		else if (overflow == 0) {
			if (sum > 0)
				cout << "+";
			else if (sum == 0)
				cout << "0";
			else
				cout << "-";
		}
		else
			cout << "-";
		cout << '\n';
	}
	
	return 0;
}