[백준/1904/파이썬] 01타일

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

1904번: 01타일

Problem

• 우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다
• 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 있다.

조건

• 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.)
• 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
• 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
• 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

SOL

타일이 끝나는 조건을 생각해주면, 타일은 1로 끝나거나, 타일은 00꼴로 끝난다고 볼 수 있다.

 

따라서, F(N) = F(N-1)+F(N-2) 라는 어디서 많이본 친숙한 점화식이 뿅하고 튀어나온다.

그림판에서 그려옴

n자리라고 했을때, 끝이 1이기 때문에, n-1로 이루어진 숫자가 올거고, 끝이 00이기 때문에, n-2로 이루어진 숫자가 올거다. 이런 풀이가 가능한 이유는, 1 또는 00으로 끝나는 경우밖에 없기 때문임.(그리고, 그 경우가 적기 때문)