BOJ 1635 1 또는 -1

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

1635번: 1 또는 -1

 

개인적으로 되게 재밌는 constructive 문제였습니다.

 

사실 증명은 아직 잘 모르겠습니다... proof by AC 했어요.

 

총 $N$개의 수열을 쓴다는 아이디어에서 출발했는데, 어떤 점을 기준으로 수열을 왼쪽과 오른쪽을 나눴을 때 왼쪽 구간의 합과 오른쪽 구간의 합이 같으면 한쪽 구간에는 -1을, 반대쪽 구간에는 1을 곱해주는 방식으로 해결할 수 있습니다. 따라서 왼쪽부터 -1로 채워지고 오른쪽부터 1로 채워진 수열 $N$개 중 하나를 이용하여 어떤 수열이든 수열값이 0이 되게 만들 수 있습니다. 다만 왼쪽 구간의 합과 오른쪽 구간의 합이 같은 지점이 항상 존재하는지는 증명을 못 했습니다.

 

+) cologne님이 증명을 알려주셨습니다.

 

수열값을 $S$라고 할 때 전부 1을 곱할 때의 수열값은 $S$, 전부 -1을 곱할 때의 수열값은 $-S$입니다. 이 때 왼쪽부터 1을 -1로 바꿔가며 곱해주는 건 함수값이 $S$에서 $-S$까지 2씩 변하는 함수이고, 따라서 그 사이에 값이 0이 되는 지점이 한 번은 존재합니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, m;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> m;

    while (m--) {
      vector<int> vec;
      vec.resize(n + 1);
      for (int i = 1; i <= n; i++) cin >> vec[i];

      vector<int> sum;
      sum.resize(n + 1);
      for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + vec[i];

      int idx = 0;
      for (int i = 0; i <= n; i++) {
        idx = i;

        int front = sum[i] - sum[0];
        int back = sum[n] - sum[i];

        if (front == back) break;
      }

      for (int i = 1; i <= idx; i++) cout << -1 << ends;
      for (int i = idx + 1; i <= n; i++) cout << 1 << ends;
      cout << endl;
    }
  }

  return 0;
}