백준 1904 01타일

문제 링크입니다: https://www.acmicpc.net/problem/1904

N-2개 수열에 00을 붙이는 가지수와 N-1개 수열에 1을 붙이는 가지수를 더한 값이 N개 수열 가지수입니다.

결국 피보나치 수열이였습니다.

/*

지원이에게 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이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다.

단 타일들은 무한히 많은 것으로 가정하자.

*/

#include <iostream>

using namespace std;

 

const int MOD = 15746;

const int MAX = 1000000;

 

int N;

int cache[MAX + 1];

 

int kindsOfBinary(void)

{

        cache[1] = 1; //1

        cache[2] = 2; //00, 11

        //3: 100 001 111 -> 3

        //4: 0000 0011 1001 1100 1111 -> 5

        //5: 10000 00001 11111 11100 00111 00100 10011 11001 -> 8

 

        //결국은 피보나치 수열이다

        for (int i = 3; i <= N; i++)

               //00을 붙이거나 1을 붙이거나

               cache[i] = (cache[i - 2] + cache[i - 1]) % MOD;

        return cache[N] % MOD;

}      

 

int main(void)

{

        cin >> N;

        if (N > MAX)

               exit(-1);

       

        cout << kindsOfBinary() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~