[BOJ 27487 // C++] One and Two

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

 

이번에 볼 문제는 백준 27487번 문제인 One and Two이다.
문제는 아래 링크를 확인하자.

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

27487번: One and Two

주어지는 모든 수는 1 또는 2이므로, 주어진 등식의 양변은 모두 \(2^k\)꼴로 나타나게 될 것임을 알 수 있다.

 

따라서 양변의 값을 같게 하기 위해서는 양변의 지수 k, 즉 곱해진 2의 개수를 같게 해주어야 한다. 이를 위해 2의 개수가 양의 짝수라면 (개수/2)번째 2의 위치가 답이 되고, 홀수라면 답이 존재하지 않으므로 -1을, 그리고 2의 개수가 0개라면 1을 출력해 문제를 해결해주자.

 

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

#include <iostream>
using namespace std;

int T, N;
int arr[1000];

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

	cin >> T;
	while (T--) {
		cin >> N;
		int cnt2 = 0;
		for (int i = 0; i < N; i++) {
			int& cur = arr[i]; cin >> cur;
			if (cur > 1) cnt2++;
		}

		if (cnt2 & 1) cout << -1 << '\n';
		else {
			if (cnt2) {
				cnt2 /= 2;
				for (int i = 0; i < N; i++) {
					if (arr[i] > 1) {
						cnt2--;
						if (!cnt2) {
							cout << i + 1 << '\n';
							break;
						}
					}
				}
			}
			else cout << 1 << '\n';
		}
	}
}