[BOJ 7347] 플립과 시프트

 문제는 여기에서 확인 가능하다.

---

 한 번 플립이 수행될 때 마다, 디스크 하나를 사이에 두고 있는 두 디스크의 위치가 바뀐다. (문제에서의 그림 참고)

 전체 디스크의 개수가 홀수이면 항상 검은 디스크와 흰 디스크를 분리할 수 있다.

 반대로 디스크의 개수가 짝수라고 하자. 어느 한 디스크부터 시계방향으로 $1$부터 $m+n$까지 번호를 붙이면, 짝수 번호를 가지고 있는 디스크는 짝수 번호의 위치로만, 홀수 번호를 가지고 있는 디스크는 홀수 번호의 위치로만 움직일 수 있다.  두 종류의 디스크 중 흰 디스크가 연속적으로 모여있으면, 검은 디스크도 연속적으로 모여있게 된다. 

 흰 디스크를 연속적으로 모으는 경우만 고려하자. 흰 디스크를 연속적으로 모을 수 있다는 것은 짝수 번호를 가진 디스크의 수와 홀수 번호를 가진 디스크의 수가 2이상 차이나지 않는다는 것과 같다. 이를 이용하면 문제를 해결할 수 있다.

 

 코드는 다음과 같다.

#include<bits/stdc++.h>
 
using namespace std;
 
int T, N, D[30];
 
int solve() {
    if(N%2) return 1;
    int even = 0, odd = 0;
    for(int i = 0; i < N; i++) {
        if(D[i]) {
            if(i%2) odd++;
            else even++;
        }
    }
    if(abs(even - odd) <= 1) return 1;
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    while(T--) {
        cin >> N;
        for(int i = 0; i < N; i++) cin >> D[i];
        if(solve()) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}