[BOJ 1904] 01타일

1) 문제 링크

https://www.acmicpc.net/problem/1004

2) 접근

연역적인 규칙이 바로 보이진 않았기에 일단 해를 나열해보았다.

N	해	합계
1	1	1
2	00, 11	2
3	100, 001, 111	3
4	0000, 1100, 1001, 0011, 1111	5
5	10000, 00100, 11100, 00001, 11001, 10011, 00111, 11111	8
…	…

1, 2, 3, 5, 8, … ㅇㅎ 피보나치네. 근데 왜 피보나치일까??
이것까진 답을 못 내고 걍 풀었다.

3) 풀이

#include <iostream>
using namespace std;
const int MAX = 91;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    int a = 0, b = 1, c = 1;

    cin >> N;

    for(int i=1; i<N; ++i){
        a = b;
        b = c;
        c = a + b;
        c = c % 15746;
    }
    cout << c;

    return 0;
}

4) 피드백

다른 사람이 쓴 글을 읽어봤는데, $N=k$일 때의 해는 ($N=k-2$일 때의 해 뒤에 ‘00’ 붙인 것)+($N=k-1$일 때의 해 뒤에 ‘1’ 붙인 것)이라서 피보나치 수열이 나온다고 했다. 근데 그래도 잘 모르겠다. 수학적 귀납법을 써서 관계를 증명해보려고 했지만, 해를 이전의 해들의 합으로 표현하는 과정에서 해의 완비성이 충족되는지도 잘 모르겠고…

(수정)이제 알겠다. 2Xn 타일링 문제랑 비슷하게 이 문제도 ‘끝’에 주목해야 한다. 결국 ‘1’또는 ‘00’으로 끝나는데, 끝을 제외한 그 앞부분 또한 ‘1’과 ‘00’으로만 구성된다. 다시 말해, $N=k$일 때 ‘1’로 끝나는 수의 앞쪽 k-1자리는 ‘1’ 또는 ‘00’으로만 구성되고, ‘00’으로 끝나는 수의 앞쪽 k-2자리는 ‘1’ 또는 ‘00’으로만 구성된다.