백준 7347번: 플립과 시프트

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

7347번: 플립과 시프트

우선 트랙의 어느 한 지점을 끊어 타원형 트랙을 직선형 트랙으로 사용한다고 생각해보자. 트랙 위 어느 디스크를 중심으로도(각 끝의 두 디스크를 제외하고) 회전 가능하고 회전 전/후의 좌표 차이는 2 혹은 그 배수이므로, 홀수번째에 있는 모든 디스크는 서로 교환이 가능하고 짝수번째에 있는 모든 디스크 역시 서로 교환이 가능하다. 이 때 모든 검은 디스크를 한 곳으로 모은 경우 검은 디스크의 좌표 중 홀수 좌표의 개수와 짝수 좌표의 개수의 차는 1 이하가 됨이 자명하므로, 직선형 트랙에서 검은 디스크를 모두 모으려면 검은 디스크의 좌표 중 홀수 좌표의 개수와 짝수 좌표의 개수의 차가 1 이하가 되어야 한다.

이제 트랙의 끊은 지점을 다시 이어 타원형 트랙으로 복구하자. 트랙에 든 모든 디스크의 개수 N이 홀수라면 맨 끝에 있는 (N - 1)번째 디스크를 회전시켰을 때의 위치는 (N - 1 - 2) 혹은 (N - 1 + 2)인데, 이 때 디스크의 개수가 N개이므로 (N - 1 + 2)번째는 (N - 1 + 2) % N = (N + 1) % N = 1이다. 이 때 N이 홀수이므로 N - 1은 짝수이고 1은 홀수이므로, 홀수번째 좌표에 있는 디스크와 짝수번째 좌표에 있는 디스크를 서로 교환할 수 있다. 즉 N이 홀수일 때는 짝수번째 디스크를 홀수번째로, 홀수번째 디스크를 짝수번째로 만들 수 있으므로 순서의 짝수/홀수가 무의미하다. 즉 N이 홀수일 때는 반드시 디스크를 한 쪽으로 몰 수 있다.

#include <cstdio>

int abs(int n) { return n < 0 ? - n : n; }

bool test_case() {
    // N: 디스크의 수, buf: 각 디스크가 검은색이라면 1, 아니라면 0
    // diff: 검은 디스크의 좌표 중 홀수 좌표의 개수와 짝수 좌표의 개수의 차
    int N, buf, diff = 0;

    // 디스크의 개수와 각 디스크를 입력받으며
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &buf);
        // 홀수 좌표와 짝수 좌표의 디스크의 개수의 차를 diff에 저장
        if (buf) diff += (i % 2 ? 1 : -1);
    }

    // N이 홀수인 경우에는 각 디스크의 좌표의 홀/짝 여부는 바뀔 수 있으므로
    // N이 홀수인 경우에는 반드시 true
    // N이 짝수이고 diff가 1 이하라면 모든 검은 디스크를 한 곳으로 모을 수 있음이 자명
    // 즉 N이 홀수거나 diff가 1 이하라면
    // 주어진 테스트 케이스는 흰색과 검은색 디스크들을 분리해 낼 수 있다
    return N % 2 || abs(diff) <= 1;
}

int main() {
    int T;
    // 테스트 케이스의 수를 입력받아 각 테스트 케이스의 정답을 출력
    for (scanf("%d", &T); T--; ) printf("%s\n", test_case() ? "YES" : "NO");
    return 0;
}