이번 문제는 실버 1 종이 접기 문제이다.
문제를 차근차근 한 번 읽어보자.
종이를 안, 밖으로 계속 접는데 접힌 방향을 보는 문제이다.
주어진 접힌 모습이 접을 수 있는 모양인지를 판단하면 된다.
제약 조건을 한 번 살펴보면, 문자열의 최대 길이는 3000이다.
단 2^n - 1 형태로 반드시 주어진다고 한다.
생각해보면 접힌 모서리는 반드시 홀수여야 하기 때문에, 당연한 말이다.
또한, 접을 수록 모서리는 2배로 증가하기 때문에 5와 같은 홀수도 불가능하다.
테스트케이스는 1000개 까지 주어진다고 한다.
이걸 만약 완전탐색으로 모든 모양을 만들어 본다고 생각해보면, 가능할까?
최대 2047의 길이에, 테스트케이스가 1000개라고 생각해보면
매번 주어지는 문자열의 길이에 맞춰 모든 경우를 만들어 본다?
이것은 시간적으로 말이 안된다.
따라서 주어진 문자열 자체로 만들 수 있는 지 판단하는 것이 맞다.
무엇을 기준으로 판단해야 할까?
날개의 모양을 기준으로
이 종이 접기에는 아주 아주 큰 특징이 있다.
가운데 접힌 모양을 기준으로 양 날개의 모양을 생각해보자.
접혀서 맞닿아있는 모서리는 서로 맞물려야 한다.
그 말인 즉슨, 바깥으로 접힌 모서리는 안으로 접힌 모서리와 맞물린다.
즉, 001 이라는 문자열은 양 끝이 맞물려 가능한 모양이지만
000은 불가능한 문자열이라는 말이 된다.
만약 더 많이 접혀서 1010101과 같이 주어진다면?
위의 모양은 불가능한 모양이다. 이유는 아래와 같다.
101101양쪽 날개가 맞물리지 않는다.- 각 날개를 떼서 봐도
101로 만들 수 없는 모양이다.
즉, 우리는 양 쪽 날개 뿐만 아니라 각 날개 안에서도 확인을 해야한다.
각 날개 안에서도 반복 확인을 해야 한다? 재귀를 통해 파고 들어야 할 것 같다.
재귀 탐색
이분 탐색을 하듯, 재귀 탐색을 하며 양쪽 날개가 서로 반대의 모양인지 확인한다.
그 말은, 1010010 과 같이 서로 반대 모양이어야 맞물린다는 말이다.
bool fold_paper(int left, int right) {
if (left >= right)
return true;
int mid = (left + right) / 2;
for (int i = 0; i < (mid - left); i++) {
if (target[left + i] == target[right - i])
return false;
}
return fold_paper(left, mid - 1);
}위의 코드대로 재귀함수를 구현하였다.
양쪽 끝 부터 가운데로 오며 탐색을하고, 가능하면 다음 탐색을 진행한다.
이 때, 날개는 한쪽만 확인하면 된다. 그 이유는 아래와 같다.
- 가장 처음 우리는 양쪽 날개가 맞물리는 모양인지 확인한다.
- 이 때, 확인이 되었다면 두 날개는 정반대의 모양일 것이다.
- 그럼 한 쪽이 마지막 깊이까지 옳은 날개이면, 반대쪽도 마찬가지인게 된다.
종이를 접으면 반대편 날개는 정반대의 모양이다 라는 아이디어가 중요한 문제였다.
실버 티어여도 이런 아이디어가 필요한 문제가 간혹 나오는 것 같다.
더 많은 연습이 필요할 것 같다.