[BOJ] 7347 플립과 시프트

2001년 ACM ICPC 예선으로 나왔던 문제입니다. 문제는 여기서 확인할 수 있습니다.

 

고등학교 2학년 때였나, 특이한 정보과학 과목을 수강했던 적이 있었습니다. 선생님께서 마지막에 문제 24개를 주시면서 여기서 95% 이상을 풀면 시험 성적에 관계없이 A+을 주겠다고 하셨던 적이 있는데, 그 중 한 문제로 처음 접했던 기억이 납니다.

 

처음에 이 문제를 봤을 때는 DP(동적계획)와 같은 방법을 사용해서 재귀적으로 풀어야 하나 하고 고민했지만, 이런 시도가 언제나 그렇듯이 잘 되질 않았습니다. Brute Force(완전탐색)으로 해볼까도 생각해봤는데, 아무래도 m+n이 10 이상 30 미만인데 30이면 전체 가능한 경우의 수가 2^30(≒10^9)정도로 조금 무리인 감이 있습니다.(게다가 저게 되는지 안되는지 체크하는 건 또 별개죠)

 

그러던 중에 같이 듣고 있던 다른 수업에서 배웠던 내용인 순열(permutation)에 대한 내용을 떠올렸고, 여기서 디스크를 플립하는 행위가 실제로는 어느 k번째 디스크와 k+2번째 디스크의 자리를 바꾸는 것과 같다는 생각을 했습니다. 그렇다면 모든 홀수번째/짝수번째 디스크들은 각각 인접한 것들과 위치를 바꿀 수 있다는 결론이 나오는데, 어떤 인접한 두 개의 위치를 바꾸는 변환을 할 수 있으면 모든 순열을 만들어낼 수 있습니다. 따라서 각각의 홀수번째/짝수번째 디스크들은 마음대로 위치를 바꿀 수 있는 것이나 다름 없다고 볼 수 있습니다. 여기서 이제 홀짝성에 따라서 문제가 조금 달라집니다.

 

우선 디스크가 모두 짝수개 있다고 생각해봅시다. 이 경우에는 홀수번째 디스크는 홀수번째 디스크들끼리, 짝수번째 디스크는 짝수번째끼리만 이동할 수 있습니다. 따라서 한 쪽에 모든 색깔을 모으기 위해서는 홀수번째에 있는 흰색(혹은 검은색)디스크와 짝수번째에 있는 흰색(혹은 검은색)디스크의 수가 많아야 하나 정도만 차이가 나야 합니다. 모든 변환이 끝난 뒤에도 홀수/짝수번째의 검은/흰색 디스크 수는 일정하게 유지가 되어야 하니까요. 물론 그게 유지가 된다면 그 안에서는 어떻게든 움직일 수 있습니다.

 

따라서 디스크가 모두 짝수개 있다면 홀수번째에 있는 흰색의 갯수와 짝수번째에 있는 흰색의 갯수가 차이가 1 이하로 나는지를 체크해주고, 그렇다면 YES를 출력하면 됩니다.

 

디스크가 모두 홀수개 있다면 이야기가 조금 달라집니다. 여기서는 홀짝성이 보존이 되지 않습니다. 예시로 디스크가 13개쯤 있다고 하고, 편의상 어디 한 지점부터 1번 2번...하고 숫자를 메겨봅시다. 그렇다면 1번 디스크는 3번과도 자리를 바꿀 수 있고, 12번과도 자리를 바꿀 수 있습니다.

 

여기서 뭔가 이상한 점이 생깁니다. 홀수번째 디스크와 짝수번째 디스크가 위치를 바꿀 수 있습니다. 그렇게 12번과 자리를 바꾸면 12번과 2번은 같은 짝수번째니까 또 어떻게 바꿀 수 있습니다. 그렇다면 결국 1번과 2번이 바뀌는 셈인데, 이는 다른 모든 인접한 디스크들에도 적용할 수 있습니다.

 

인접한 두 디스크를 바꾸는 변환이 가능하면 모든 permutation들을 만들어낼 수 있으므로 디스크가 모두 홀수개 있다면 더 생각할 것도 없이 언제나 가능합니다.

 

이제 구현을 하는 게 문제인데, 우선 제가 주로 사용하는 Python 3.7로 구현하는 것은 별로 어려운 문제가 아니었습니다.

 

for i in ' '*int(input()):
    L=list(map(int,input().split()))[1:]
    if len(L)%2==1:print('YES') #디스크가 홀수개면 언제나 yes
    else:
        c=0
        for i in range(0,len(L),2):
            c+=L[i]
        print(['NO','YES'][c in[sum(L)/2,(sum(L)+1)/2]]) #디스크가 짝수개이면 짝수번째 것들에 있는 검정색(혹은 흰색)의 개수가 홀수 번째와 1개 이상 차이가 안 나는지 판정 후 yes 혹은 no 출력

 

그러나 PS는 특히, Python으로만 할 수는 없는 노릇이라(당장 ICPC 대회만 해도 예선부터 Python은 사용 불가능합니다.)어쩔 수 없이 C++로 구현하는 연습도 해보려고 했습니다.

 

#include<bits/stdc++.h>
using namespace std;

int L[30];

int solve(int N){
    if(N%2==1)return 1;
    int even=0;
    int odd=0;
    for(int i=0;i<N;i++){
        if(L[i]==1){
            if(i%2==1)odd++;
            else even++;
        }
    }
    if(-1<=(even-odd)&&(even-odd)<=1) return 1;
    return 0;
}

int main(){
    int T;
    int N;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i=0; i<N; i++)cin>>L[i];
        if(solve(N)==1)cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    return 0;
}

아무래도 이 블로그는 운영하면서 Python으로 이미 잘 풀었던 문제를 다시 C++로 짜면서 연습하는 과정도 올리게 될 것 같습니다.