백준 1802번: 종이접기

문제를 이해하는데 시간이 좀 걸린다.

종이를 이리저리 접어보며 규칙을 찾는데 성공

 

맨 처음 중앙의 접힌 면을 기점으로 1번으로 접으면 1 (1) 0이 만들어지고,

2번으로 접으면 0 (1) 1 이 만들어진다.

 

여기에서 한 번 더 접으면 기존의 접힌 면을 기점으로 앞 뒤에 10 또는 01이 생긴다.

 

재귀함수를 사용하여 앞 뒤 숫자가 다르면 No를 출력해주었다.

import java.util.Scanner;
import java.util.Arrays;


public class Main {

    public static int devide(char[] x, int left, int right){

        int mid = (left+right) / 2 ;

        if(right - left > 3) {
            int check = devide(x, left, mid-1);
            if (check == 0) {
                return 0;
            }
            check = devide(x, mid + 1, right);
            if (check == 0) {
                return 0;
            }
        }

        for(int i=left, k=right;i<mid;i++,k--){
            if(x[i] == x[k]){
                return 0;
            }
        }

        return 1;

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        sc.nextLine();
        String x;

        for(int i = 0;i<T;i++){
            x = sc.nextLine();

            int len = x.length();
            char[] split = new char[len];

            split = x.toCharArray();
            int check = devide(split,0,len-1);

            if(check == 1){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }


        }
    }
}