백준 종이접기 1802
1802번: 종이 접기
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1
www.acmicpc.net
문제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class boj1802 {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int tests = Integer.parseInt(reader.readLine());
for (int i = 0; i < tests; i++) {
if (foldable(reader.readLine()))
System.out.println("YES");
else System.out.println("NO");
}
}
// 종이의 굴곡이 0과 1로 문자열로 주어진다.
// 1000110
private boolean foldable(String paper) {
// assert paper.length() % 2 == 1;
// 굴곡이 하나라면 확인할 필요가 없다. 반 접었으니
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++) {
// 중간 지점에서 i만큼 + 또는 - 한 위치의 굴곡을 확인한다.
// 굴곡의 모양이 일치하는 경우 조건이 만족되지 않는다.
if (paper.charAt(half + i) == paper.charAt(half - i))
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
new boj1802().solution();
}
출력결과
3
0
000
1000110
YES
NO
YES
'Algorithm' 카테고리의 다른 글
퀵 정렬(Quicksort) 알고리즘 (0) | 2023.07.11 |
---|---|
백준 1992 쿼드트리 (0) | 2023.07.11 |
병합 정렬 (Merge Sort) 알고리즘 (0) | 2023.07.10 |
분할 정복 알고리즘 Divide & Conquer (0) | 2023.07.10 |
백준 13305 주유소 (0) | 2023.07.10 |