[BOJ] 1904번. 01타일

#. Problem

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

* The copyright in this matter is in BOJ

지원이에게 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들은 무한히 많은 것으로 가정하자.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 무한히 많은 00, 1 이 적힌 타일로 길이가 N인 만들 수 있는 모든 가짓수를 세는 것

    - 출력으로 결과값에서 15746으로 나눈 나머지를 출력 

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. N = 1, [ 1 ], 1가지

     N = 2, [00, 11], 2가지

     N = 3, [001, 100, 111], 3가지

     N = 4, [0000, 0001, 0011, 1001, 1100],  5가지

     N = 5, [00001, 00111, 11111, 10000, 11100, 10011, 11001, 00100], 8가지

  2. N은 1, 2, 3, 5, 8, 13, ... 와 같이 피보나치 수열의 규칙을 가지고있다.

  3. 결국 N번째 피보나치 수열의 값을 찾는 것.

  4. 출력으로 결과값에서 15746으로 나눈 나머지를 출력 

#. Code

#include <iostream>
#include <cstring>
 
using namespace std;
 
int MOD = 15746;
int fb[1000001] = { 0, 1, 2 };
 
int main() {
    // Improving iostream performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    
    int n;
    cin >> n;
 
    for (int i = 3; i <= n ; i++) {
        fb[i] = (fb[i - 1] + fb[i - 2]) % MOD;
    }
 
    cout << fb[n] % MOD;
 
    return 0;
}

#. Result

  - Input --------------------------------------------------------

4

------------------------------------------------------------------

  - Output --------------------------------------------------------

5

------------------------------------------------------------------