취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23615번 문제인 Product이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/23615

입력으로 주어지는 수가 0 또는 음의 정수일 수 있다는 점에 유의하자.

주어지는 수에 0이 포함되어 있는 경우, 0이 하나라면 불가능하고 둘 이상이면 항상 가능함을 어렵지 않게 관찰할 수 있다. 아래에서는 주어지는 수에 0이 포함되어있지 않은 경우만을 생각한다.

어떤 한 수와 다른 모든 수의 곱이 같다는 것은 그 하나의 수가 모든 수의 곱의 제곱근과 같아야 함을 관찰할 수 있다. 이 때 제곱근은 양의 제곱근과 음의 제곱근 둘 중 어떤 것이어도 상관없다. 이를 이용하면 풀이를 어렵지 않게 구성할 수 있다.

그러나 모든 수의 곱으로 가능한 값은 매우 크므로 직접 모든 수를 곱하는 것은 매우 느릴 것이다. 이 부분은 어떻게 최적화할 수 있을까? 간단한 방법 중 하나는 주어지는 수의 절댓값이 10억 이하임을 이용하는 것이다. 구체적으로, 이 중 하나의 값이 제곱근이어야 하므로 모든 수의 곱의 절댓값이 10억의 제곱보다 커진다면 주어진 수에서 제곱근을 더 이상 고를 수 없음을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef __int128 lll;

lll prd = 1; ll L, R;
int zcnt; bool WA;

int N;
vector<int> vec;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N; vec.reserve(N);
	while (N--) {
		int x; cin >> x;
		if (x == 0) {
			zcnt++;
			continue;
		}
		prd *= x;
		if (prd > 1000000000000000000LL || prd < -1000000000000000000LL) WA = 1;
		if (WA) continue;
		vec.emplace_back(x);
	}
	if (zcnt) {
		if (zcnt == 1) cout << "No";
		else {
			cout << "Yes" << '\n';
			cout << 0;
		}
		return 0;
	}
	if (WA || prd < 0) {
		cout << "No";
		return 0;
	}

	L = 1, R = 1000000000; 
	while (L < R) {
		ll mid = (L + R) / 2;
		if (mid * mid < prd) L = mid + 1;
		else R = mid;
	}
	if (L * L != prd) {
		cout << "No";
		return 0;
	}

	for (auto &x:vec) {
		if (abs(x) == L) {
			cout << "Yes\n";
			cout << x;
			return 0;
		}
	}
	cout << "No";
}