취미로 코딩하기

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

이번에 볼 문제는 백준 1635번 문제인 1 또는 -1이다.
문제는 아래 링크를 확인하자.

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

주어지는 수열\(a_1 \cdots a_N\)은 다음과 같은 두 가지 성질이 있다.

(1) \(a_1 + \cdots + a_N\)은 짝수이다.

(2) 1에서 계산한 값이 0이 아니라면, \(a_1 + \cdots + a_k = a_{k+1} + \cdots + a_N\)을 만족시키는 \(1\le k<N \)인 정수 \(k\)가 존재한다. (증명은 값이 contiguous하게 변한다는 점을 이용해 IVT(중간값 정리)와 유사하게 가능하다.)

2의 식의 우변을 좌변으로 넘기면 각 항에 1 또는 -1을 곱해 총합이 0이 되게 계수를 설정하는 방법을 하나 항상 얻을 수 있다. 또한 이 때 나올 수 있는 \(b_i\)의 가짓수는 \(k\)의 가짓수와 같으므로 총 \(N-1\)가지임을 알 수 있다.

1에서 계산한 값이 0인 경우 \(b_i\)의 값을 모두 1로 두어 조건을 만족시킬 수 있음을 추가로 관찰하면, 총 \(N\)가지의 \(b_i\)를 이용해 주어진 모든 식을 0으로 항상 만들 수 있음을 확인할 수 있다.

위 내용을 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, M;
int A[102];

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

	cin >> N >> M;
	while (M--) {
		int total = 0;
		for (int i = 1; i <= N; i++) {
			cin >> A[i];
			total += A[i];
		}
		if (!total) {
			for (int i = 1; i <= N; i++) {
				cout << 1 << ' ';
			}
			cout << '\n';
		}
		else {
			int psum = 0;
			for (int i = 1; i <= N; i++) {
				psum += A[i];
				if (psum * 2 == total) {
					for (int k = 1; k <= i; k++) {
						cout << 1 << ' ';
					}
					for (int k = i + 1; k <= N; k++) {
						cout << -1 << ' ';
					}
					cout << '\n';
					break;
				}
			}
		}
	}
}

BOJ Random Defense #20