종이 접기( BOJ 1802 )

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

1802번: 종이 접기

 

문제 파악하기

항상 종이를 절반씩 접는다고 할 때, 제시된 문자열로 종이를 접을 수 있는지 확인하는 문제입니다. 종이를 절반씩 접게 되면, 항상 접은 부분을 중심으로 양쪽에는 반대로 접힌 흔적이 남게 됩니다. 이를 활용하면 문제를 해결할 수 있습니다.

 

문제 해결하기

종이를 접어 생기는 흔적은 항상 중앙에 생기게 됩니다. 그리고 생긴 흔적을 중심으로 항상 반대로 접히게 됩니다. 예를 들어 문자열이 1000110 인 경우, 처음 접은 흔적은 1000110 정중앙에 위치한 0입니다. 그 다음 접은 흔적은 1000110 가운데 0을 기준으로 나눠진 3개의 흔적 중 중앙에 위치한 0과 1입니다. 마지막으로 접은 흔적은 1000110 남은 4개의 흔적이 됩니다. 따라서 이 문자열은 종이를 총 3번 접었으며, 우리는 이렇게 종이를 접을 때마다 나올 수 있는 문자열인지 확인하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 3010
 
int T;
char inp[NMAX];
 
int l, r, mid, f;
 
void sv(int l, int r) {
    int mid, ll, rr;
 
    if(!f or l>r) return;
 
    mid = (l+r)/2;
    for(ll=mid-1,rr=mid+1;ll>=l and rr<=r;ll--,rr++) {
        if(inp[ll] == inp[rr]) {
            f = 0;
            return;
        }
    }
 
    sv(l, mid-1);
    sv(mid+1, r);
}
 
int main() {
    scanf("%d", &T);
    while(T--) {
        inp[0] = '\0';
        scanf("%s", inp);
 
        f = 1;
        sv(0, strlen(inp)-1);
 
        if(f) printf("YES\n");
        else printf("NO\n");
    }
}

후기

문제를 해결하는 알고리즘은 어렵지 않지만 떠올리는 추상화 과정이 어려운 문제라고 생각합니다. 분할 정복을 연습하는 사람에게 추천하고 싶은 문제입니다.