[JAVA]1802 종이접기 분할정복

 📚 문제  

1802번: 종이 접기

 

🔍 아이디어  

종이의 반을 접는 경우 A | B 와 같다면 A와 B는 접는기준으로 대칭적이라는 특징이 있다.

해당 특징을 이용하여 중간점을 기준으로 A와 B가 대칭인지 확인하고 A와 B종이도 종이의 절반을 기준으로 대칭적인지 계속해서 재귀적으로 탐색한다.

 

예제 입력

3
0
000
1000110

예제 출력

YES
NO
YES

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(br.readLine());
        while (tests-- > 0) {
            if (foldable(br.readLine())) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private boolean foldable(String paper) {
        if (paper.length() > 1) {
            int half = paper.length() / 2;

            //왼쪽 종이와 오른쪽 종이가 가능한 경우인지 확인한다.
            if (!foldable(paper.substring(0, half))) return false; //왼쪽
            if (!foldable(paper.substring(half + 1))) return false; //오른쪽

            //접혔던 작은 부분들이 가능한 경우라면 현재 페이지에서 서로 반대 방향이 되는지 확인한다.
            for (int i = 1; i < half + 1; i++) {
                if (paper.charAt(half - i) == paper.charAt(half + i)) {
                    return false; //둘이 같으면 안된다. (서로 반대 방향이여야 한다)
                }
            }
        }

        //반으로 접은 경우이므로 1페이지인 경우 확인하지 않아도 된다.
        return true;
    }
}