[백준OJ] 7347번 플립과 시프트

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

7347번: 플립과 시프트

---

 

 

풀이

먼저 처음봤을때 m+n값이 30이하라서 모든 경우의수를 체크해보려했는데, 문제에서 특정횟수 수행이아닌, 유한번 수행해서 성공여부를 판단하라 해서 다른 방법을 생각해봤다.

 

먼저 디스크의 중앙을 기준으로 좌 <-> 우 를 교체하는 플립과정을 봤을때,  검 흰 검 흰 이 있다고 하면 어떻게 바꾸든 이어지지 못한다. 위의 기준을 만족하기 위해서는 홀수번째 인덱스에 검은색이 있어야 한다.

 

위를 생각하니 N+M이 짝수인 경우에는 구하기가 쉬워졌다. 짝수일때 플립은 규칙이 쉽다. 어떤 경우로 어떻게 돌리더라도 짝수번째 인덱스는 짝수번째와 플립이되고, 홀수번째 인덱스는 홀수번째 인덱스와 플립이 된다.

 

따라서 아래의 그림과같이 짝수번째 인덱스에 모든 검은색이 있으면 절대 모을수가 없다. 홀수번째도 마찬가지다 (어떤 검은원판을 옮기더라도 결국 0번째 원판과 2번째 원판이 같이 돌아가므로)

따라서 N+M이 짝수라면, 홀수번째 검은원판의 개수와 짝수번째 원판의 개수가 같거나, 1개의 차이를 내야한다.같으면 "짝홀짝홀" 배치가 가능해지고, 1개의 차이를 내면 "짝홀짝" 혹은 "홀짝홀"의 배치가 가능해진다.

 

그럼 다음 N+M이 홀수인 경우를 알아보자. 홀수인 경우에는 짝수는 짝수끼리, 홀수는 홀수끼리 돌아간다는 절대적인 법칙이 성립하지 않는다. 왜냐하면 짝수번째 위치의 원판을 옆으로 계속 플립을하면 홀수번째 위치로 갈 수 있고, 홀수번째는 반대로 짝수번째 위치로 갈 수 있기때문이다. 

따라서 N+M이 홀수인 경우에는, 어떠한 경우라도 한곳으로 모을 수 있게된다.

 

정리하면 가능한 경우는 다음과 같다.

1. N+M이 짝수이면서 |짝수번째 검은원판의 개수-홀수번째 검은원판의 개수| <=1

2. N+M이 홀수 

시간복잡도

간단하게 입력을 받으면서 체크할 수 있기때문에 O(T(N+M))

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();

        while((t--)>0){
            int even=0;
            int odd=0;
            int n=sc.nextInt();
            for(int i=0;i<n;i++){
                int temp=sc.nextInt();
                if(i%2==0&&temp==1){
                    even++;
                }
                else if(i%2==1&&temp==1){
                    odd++;
                }
            }
            if(n%2==1 || (n%2==0 && Math.abs(even-odd)<=1)){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
        }
    }
}