[백준] 플립과 시프트

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

 

문제요약 : 회전하는 판에 검은색 흰색 돌이 있는데 한 돌을 기점으로 좌우 돌을 스왑할 수 있다. 검은돌과 흰돌이 섞여있지 않게 놓을 수 있는가?

 

※흰 원판 검은 원판이긴 한데 그냥 넘어갑시다.!

 

조건 :

1. 테스트 케이스 수 T 제한 x

2. 흰돌 개수 m, 검은돌 개수 n에 대해 10≤m+n≤30

3. 흰 돌은 0, 검은 돌은 1로 주워진다.

 

해설 :

전체 개수 N이라 할 때 (N=m+n) 검은 돌에 대해서만 생각해보자(검은 돌이 한쪽에 몰려있으면 다른쪽에 흰돌이 몰려있다)

i)N이 짝수인 경우

검은 돌의 위치를 2로 나눈 나머지가 홀수인 경우 a, 짝수인 경우 b라 할 때

abs(a-b)≤1이면 검은 돌을 한 쪽에 몰아넣을 수 있다.

왜냐하면 N이 짝수이므로 돌을 스왑시켜도 그 돌의 위치를 2로 나눈나머지는 스왑 전과 같기 때문이다

 

ii)N이 홀수인 경우

짝수인 경우는 한바퀴 회전해 와도 돌의 위치를 2로 나눈 나머지는 원래 위치를 2로 나눈 나머지와 같지만

홀수인 경우 한바퀴 회전해서 돌아오면 돌의 위치를 2로 나눈 나머지 값은 바뀐다 (짝수->홀수, 홀수->짝수)

즉 돌의 위치를 2로 나눈 나머지 값을 임의로 바꿀 수 있기에 어떠한 쿼리가 들어와도 YES를 출력하면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int T, a, c, d, n, i;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(i=c=d=0; i<n; i++) scanf("%d",&a), (i%2?c:d)+=a;
        (n%2)?printf("YES\n"):printf((abs(c-d)<=1)?"YES\n":"NO\n");
    }
}