[백준알고리즘] 1802번: 종이 접기 -C++

[백준알고리즘] 1802번: 종이 접기 -C++

1802번: 종이 접기 (acmicpc.net)

1802번: 종이 접기

문제만 읽었을 때는 되게 어려운 문제라고 생각했다. 문제를 푸는 방법을 찾았을 때도 시간 초과가 괜찮을지 걱정했었는데 여유로운 시간이었다. 정답 비율만 보고 살짝 어려운 문제인가 싶었는데 실버 문제는 실버 문제였다.

분할 정복으로 분류되어 있는데, 분할 정복인가.. 싶긴 하다.

---

문제 풀이

문제의 내용은 사실 대부분이 불필요한데 괜히 길다. 아무튼 원룡이가 막 접었다가 피었을 때의 접힌 자국 그대로 동호 규칙을 적용해서 접을 수 있는가에 대한 문제다. 동호 규칙은 항상 주어진 종이를 반으로 접는 것이다.

 

문제에서 접으면 두께가 2배가 된다는 거랑 위로 접는 방법이랑 아래로 접는 방법 두 가지가 있다는 내용 모두 불필요하다.

0이든 1이든 서로 반대로만 접힌다고 생각하면 된다.

 

문제를 푸는 규칙은 간단하다. 문자열이 주어졌을 때 가운데 부분을 찾는다. 가운데를 기준으로 좌우로 한 칸씩 멀어지면서 좌우의 값이 달라야 한다. 좌측 값이 0일 때는 우측 값이 1이 되어야 하고, 좌측 값이 1일 때는 우측 값이 0이어야 한다. 그래야 정가운데를 기준으로 종이를 접었을 때 접히는 부분이 겹치게 된다.

만약 좌측 값들과 우측 값들이 모두 달라 접을 수 있다면, 가운데를 기준으로 나눴을 때의 한쪽 측면의 값들만 이용해서 반복하면 된다. 즉, 가운데를 기준으로 접힌다면 가운데를 기준으로 왼쪽면을 사용하든 오른쪽면을 사용하든 상관없다는 것이다. 나는 계속해서 좌측 값들로 주어진 문자열을 반으로 나눠서 사용했다.

 

아래는 소스코드다.

#include <cstdio>
#include <string>
#include <iostream>

int inputTestCase();
void solve();
bool checkFolding(const std::string &sSequential, const size_t siLeftRange, const size_t siRightRange);

int main(void) {
	int iCase = inputTestCase();

	for ( int i = 0; i < iCase; ++i ) {
		solve();
	}
}

int inputTestCase() {
	int iCase = 0;
	scanf("%d ", &iCase);
	return iCase;
}

void solve() {
	std::string sSequential;
	std::getline(std::cin, sSequential);

	if ( true == checkFolding(sSequential, 0, sSequential.size() - 1) ) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}
}

bool checkFolding(const std::string &sSequential, const size_t siLeftRange, const size_t siRightRange) {
	if ( siLeftRange == siRightRange ) {
		return true;
	}

	const size_t siMiddleOffset = (siLeftRange + siRightRange) / 2;

	size_t siLeftOffset = siMiddleOffset - 1;
	size_t siRightOffset = siMiddleOffset + 1;
	while ( 0 <= siLeftOffset && siRightOffset <= siRightRange ) {
		if ( sSequential[siLeftOffset] == sSequential[siRightOffset] ) {
			return false;
		}
		siLeftOffset--;
		siRightOffset++;
	}

	return checkFolding(sSequential, siLeftRange, siMiddleOffset - 1);
}