[Java] BOJ1802, 백준 - 종이 접기

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

1802번: 종이 접기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128MB	621	192	158	31.474%

문제

동호는 종이를 접는데 옆에서 보고 접으려고 한다. 옆에서 본다는 말은 아래 그림과 같이 본다는 뜻이다. 동호는 종이를 반으로 접을 때, 아래와 같이 두가지중 하나로만 접을 수 있다.

1. 오른쪽 반을 반시계 방향으로 접어서 왼쪽 반의 위로 접는다.
2. 오른쪽 반을 시계 방향으로 접어서 왼쪽 반의 아래로 접는다.

아래의 그림은 위의 설명을 그림으로 옮긴 것이다.

한 번의 종이 접기가 끝났을 때, 동호는 종이 접기를 원하는 만큼 더 할 수 있다. 종이 접기를 한번 접을 때 마다 두께는 2배가 되고 길이는 절반이 될 것이다.

종이 접기를 여러 번 했을 때 (안접을 수도 있다), 동호는 종이를 다시 피기로 했다. 그러고 나서 다시 접고 이렇게 놀고 있었다. 옆에서 보고 있던 원룡이는 동호를 위해 종이를 접어서 주기로 했다.(원룡이는 동호의 규칙대로 접지 않는다.) 동호는 그리고 나서 원룡이가 접었다 핀 종이를 다시 동호의 규칙대로 접을 수 있는지 궁금해졌다.

위의 저 종이를 접었다 피면 다음과 같은 그림처럼 펴진다.

종이가 시계방향으로 꺽여있으면 OUT이고, 반시계방향으로 꺾여있으면 IN이다.

종이가 접혀있는 정보가 왼쪽부터 오른쪽까지 차례대로 주어졌을 때, 이 종이를 동호의 규칙대로 접을 수 있는지 없는지를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1은 위의 그림에서 OUT을 의미하고 0은 위의 그림에서 IN을 의미한다. 예를 들어, 위의 그림과 같은 모양은 100으로 나타낼 수 있다. 문자열의 길이는 3000보다 작으며, 항상 2^N-1꼴이다. (N>=1)

 

출력

T개의 줄에 차례대로 각각의 종이를 동호의 방법대로 다시 접을 수 있으면 YES를, 접을 수 없으면 NO를 출력한다.

 

<풀이>

종이를 여러 번 접게되면 가운데를 기준으로 양 쪽의 종이 접은 모양은 정반되가 되어야 할 것이다.

예를 들어 왼쪽이

110 일 경우에, 가운데는 0/1 뭐가 오든 상관없지만 오른쪽은 정반대의 모양인 001이 되어야 할 것이다.

즉 이 문제의 포인트는

1. 가운데는 바깥으로 접든 안쪽으로 접든 상관이 없다.
2. 가운데를 기준으로 왼쪽의 접은 모양과 오른쪽의 접은 모양은 정반대의 모양이어야 한다.

는 것이다.

이걸 계속 해주면 된다.

예를들어 예시의 경우

1101001에서 가운데 1을 기준으로 110와 001을 비교하고, 그 다음에는

둘 중 하나만 가지고 비교한다.

110을 가지고 비교해보자. 가운데 1을 기준으로 1과 0으로 정반대이기 때문에 다음

다음은 1이다. 비교할 게 더 없으니 이 종이는 가능한 경우이다. YES출력

 

다른 예시를 들어보자

 

100000110111110 > 1000001 > 100 > 1

YES

이런식으로 하나만 남을때까지 문자열의 반을 쪼개서 같은 방법으로 비교해주면 된다.

재귀를 이용해서 풀었다.

 

시간복잡도

문자열의 길이는 3000보다 작으며, 항상 2^N-1꼴이기 때문에 최대 문자열의 길이는

N=11일 때, 2047

탐색은 문자열의 길이/2 만큼까지만 이루어진다.

그러면 수식으로는 아래와 같이 되는데, 사실 저 수식을 계산하면 원래 문자열의 길이와 같아진다.

그러므로 최대 경우의 수는 2047

 

+메모리는 신경 안써도 될 수준이다.

 

소스코드1 - 커서를 이용

import java.io.*;
import java.util.*;

public class Main {

	private static boolean check;
	private static String s;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			s = br.readLine();
			check = true;
			fold(0, s.length() - 1);
			if (check)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}

	private static void fold(int start, int end) {
		if (end <= 1)
			return;
		// 해당 문자열의 가운데를 기준으로 양쪽을 비교한다.
		// 만약 접을 수 있는 모양이라면 가운데를 기준으로 왼쪽까지만
		int left = start;
		int right = end;

		while (left < right) {
			if (s.charAt(left++) == s.charAt(right--)) {
				check = false;
				return;
			}
		}

		fold(0, right - 1);
	}
}

 

소스코드2 - for문으로 문자열을 비교

import java.io.*;
import java.util.*;

public class Main {

	private static boolean check;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			String s = br.readLine();
			check = true;
			fold(0, s.length() - 1, s);
			if (check)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}

	private static void fold(int start, int end, String s) {
		if (s.length() <= 1)
			return;
		// 해당 문자열의 가운데를 기준으로 양쪽을 비교한다.
		// 만약 접을 수 있는 모양이라면 가운데를 기준으로 왼쪽까지만
		// 가운데점은 s.length()/2
		String s1 = s.substring(0, s.length() / 2);
		String s2 = s.substring(s.length() / 2 + 1, s.length());

		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) == s2.charAt(s2.length() - i - 1)) {
				check = false;
				return;
			}
		}

		fold(0, s1.length() - 1, s1);
	}
}