백준 7347 플립과 시프트(C++)

 

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

7347번: 플립과 시프트

위와 같은 문제입니다. 문제에서 말하는 플립을 쉽게 말하면 한칸떨어진 원판과 위치를 바꿀수 있다는 것입니다. 여기서 우리가 생각해봐야 할것은 항상 한칸 떨어진 원판과 바꾼다는 점입니다.

수열이 원형으로 이어졌다고해서 어렵게 생각할 필요없습니다. 이 수열은 길이가 홀수인 수열과 길이가 짝수인 수열로 나눠 생각해볼수 있습니다. 

예시를 들어 설명해드리겠습니다.

위는 길이가 짝수인 수열입니다. 원판들이 플립될 수 있는 범위를 표시했습니다. 예시를 보면 알수있듯이 짝수인 수열들은 결국 갈수있는(플립할수있는)위치가 정해져있는걸 보실수있습니다.

 

길이가 홀수인 수열은 반대로 한 원판이 갈수있는 범위가 전체 수열에 해당합니다. 따라서 길이가 홀수인 수열은 항상 어떤 수열의 상태든 만들수있습니다. 문제가 요구하는 흰색원판과 검은색원판들이 연속된 상태로도 만들 수 있습니다.

 

이제 길이가 짝수인 수열로 돌아와서 위에 표시된 범위들을 보고 알아낼 수 있는 사실이있습니다. 정해진 위치들은 어떤 한 원판의 기준으로 잡았을때 항상 홀수번째 위치 또는 짝수번째에 위치한다는걸 알수있습니다.

 

이를 통해 문제에서 요구하는 연속된 상태로 가는것은  홀수번째에 위치한 원판과 짝수번째에 위치한 원판의 개수와 관계있다는것을 확인할수있습니다.  왜냐하면 연속된 상태는 홀수번,짝수번 번갈아 같은색 원판이 존재해야하기 때문입니다.

이제 우리는 길이가 짝수인 수열에서 홀수번째에 존재한 같은색의 원판, 짝수번째에 존재하는 같은색의 원판의 개수를 세고 만약 한쪽이 두개를 넘기면 연속된상태로 절대 갈수없다는 사실을 알수있습니다.

어느 색을 골라서 확인하든 한색깔이 연속된상태면 다른색도 연속된상태가 되므로 상관없습니다.

아래는 코드입니다.

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int N;
bool solve(vector<int> vec){
    if(N%2==1) return true;
    int count1=0;
    int count2=0;
    for(int x=0;x<N;x++){
        if(vec[x]==0 && x%2==0){
            count1++;
        }
        if(vec[x]==0 && x%2==1){
            count2++;
        }
    }
    if(abs(count1-count2)>1) return false;
    return true;
}
int main(){
    int T;
    scanf("%i",&T);
    for(int test=0;test<T;test++){
        vector<int> vec;
    scanf("%i",&N);
    for(int x=0;x<N;x++){
        int input;
        scanf("%i",&input);
        vec.push_back(input);
    }
    if(solve(vec)){
        printf("YES\n");
    }
        else{
            printf("NO\n");
        }
    }
}