이 문제는 친구가 재밌게 풀었다며 추천해준 덕에 접해보게 됐다. 결론부터 말하면 쉽게 풀지 못했다. 피보나치 수열이라는 사실을 다 풀고 나서 깨달았기 때문이다. 어렵게 해결한게 괜시리 부끄럽고 다른 접근 방식을 스스로 생각해 본 것이 재밌기도 했다.
문제
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.
어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.
그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.
입력
첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력
첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
고민 과정
이 문제를 처음 접근할 때 무식한 방법으로 해결할 경우 어떻게 될지 생각해보았다. 길이가 N인 비트열을 0부터 2의 N제곱 - 1까지 점차 증가시키면서 각 비트열이 올바른지 하나하나 확인하는 것이었는데, 당연게도 제한시간안에 수행되는 것이 불가능하다.
다음으로 고민했던 것은 길이가 n인 비트열을 만들때 길이가 n보다 작은 비트열들을 어떻게 이용할 수 있을까였다. 길이가 n-1인 비트열의 양 끝단에 1을 한 번씩 붙이고 떼면 길이가 n인 비트열 2개가 만들어지는데, 중복되는 경우가 발생하며 이런 경우의 수를 고려하는 것은 (가능은 하겠지만) 간단하지도 않을 뿐더러, 제한시간을 시킬 수 없으리라 판단해 기각했다. 이 과정에서 길이가 n인 비트열 중 길이가 n-1인 비트열로 만들 수 없는 경우는 의외로 간단하게 계산이 되기도 하였다.
(f(n)은 길이가 n이고, 조건을 만족시키는 비트열의 개수이다.)
이 케이스는 비트열의 양 끝이 0으로 끝나는 경우이다.
00 1 xxx 00 00
00 00 xxx 00 00
00 00 xxx 1 00
00 1 xxx 1 00 의 경우를 생각해볼 수 있었다. f(n-6), f(n-7), f(n-8)을 이용해 계산 가능하지만, 이용하지 않기로 하였다.
해결
유효한 비트열의 정 중앙을 나눠서 왼쪽 부분과 오른쪽 부분으로 분할해봤다. 왼쪽 오른쪽 부분 비트열을 각각 L, R이라고 하고, L이 유효한 비트열이면 R도 유효하다는 규칙을 찾을 수 있었다. 그리고 L이 유효하지 않으면, R도 유효하지 않았다.
L과 R이 유효한 경우로 만들어지는 길이가 n인 비트열의 개수는 f(L부분 길이) x f(R부분 길이) 였다. 부분 비트열이 유효한 경우엔 이렇듯 쉽게 계산이 됐지만, 유효하지 않은 부분은 그렇지 않았다. 직관적으로 보았을 때 우효하지 않은 두 부분 비트열이 L,R이라는 위치에 종속적이었기 때문이다.
(이 사진은 내 네이버 블로그에 작성했던 동일 문제 풀이의 점화식이다.)
저 A를 구하기 위해 골똘이 고민하다가 L과 R이 접한 부분이 00으로 이루어진다는 사실을 알았다. 다시말해 유효하지 않은 L, R이 유효한 길이 n의 비트열을 구성하려면 L의 오른쪽 끝은 0이고, R의 왼쪽 끝도 0이어야 한다는 것이다. 이 0을 제외한 부분은 또한 유효하였기 때문에 f(L의 길이 - 1), f(R의 길이 - 1)의 값을 이용해 간단히 알 수 있었다.
f(0)은 0이고, f(1)은 1이다. N은 2보다 크거나 같다.
이를 프로그래밍 하여 제출하니 문제가 해결됐다.
사실 이문제는 이렇게 장황하게 설명할 필요가 없던 문제였다. 1부터 8, 적어도 4까지만 살펴보면 f(n) = f(n-1) + f(n-2)(단, f(1) = 0, f(0) = 0)이며 피보나치 수열일지도 모른다는 생각을 해볼만도 하다. 또는 문제의 정의 자체가 피보나치 수를 의미하는 점을 파악할 수 있을지도 모른다. 결국 풀고 나서 '아 피보나치 수열이었구나' 하고 알게 됐다.(다른 사람들 코드가 너무 짧은 점이 의아해서 확인해보고 눈치챘다.)
