📕문제

[Baekjoon] 1904. 01타일

문제 설명

하나의 타일로 이루어진 1과, 두개의 타일로 이루어진 00 타일이 존재할 때 N개의 타일로 만들 수 있는 이진수열의 종류가 몇개인지 구하는 문제다.

---

📝풀이

N = 1 일 때 만들 수 있는 이진수열은 1 1개.
N = 2 일 때 만들 수 있는 이진수열은 11, 00로 2개.
N = 3 일 때는 111, 100, 001로 3개.
N = 4 일 때는 1100, 0000, 1111, 1001, 0011로 5개다.

쭉 구하다 보면 규칙을 발견할 수 있다.
바로 n개의 타일로 만들 수 있는 이진수열은 n-2개의 타일로 만들 수 있는 이진수열에 00타일을 붙이는 것과 n-1개의 타일로 만들 수 있는 이진수열에 1타일을 붙이는 것으로 이루어진다는 것이다.
위 규칙으로 점화식을 세워보면 $f(n) = f(n-2) + f(n-1)$ 이 된다.
이는 피보나치 수열과 같다.

import sys
read = sys.stdin.readline

N = int(read())

prev = 1
curr = 1

for _ in range(N-1):
    tmp = prev
    prev = curr
    curr = (curr + tmp) % 15746

print(curr)

• prev와 curr를 이용해 피보나치 수열을 구현했다.