[백준] 1904번 01타일 [Python] - 피보나치 수열

00과 1로 N자리수 이진수를 만드는 경우의 수 구하는 문제

$($경우의수를 15746로 나눈 나머지 출력$)$

문제

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

입력

첫 번째 줄에 자연수 N이 주어진다. $($1 ≤ N ≤ 1,000,000$)$

출력

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

1904번: 01타일 $acmicpc.net$

 

처음에는 가짓수를 구하는 문제라서  조합으로 생각했는데, 숫자가 너무 커서 시간초과가 나왔어요.
그래서 좀 더 생각해 보니까 피보나치 수열 값이랑 같았어요.
리스트랑 딕셔러니로 접근했다가 그냥 변수로 푸는 게 시간 초과에 안걸리더라고요.

이건 시간 초과 된 조합으로 접근한 코드예요.

n 자리수를 만들기 위해서 00을 i 개 사용하는 경우

00을 한 자리 수처럼 취급합시다.

그러면 n-i 자리수가 되고, 그중에서 00이 들어갈 i개의 위치를 고르면 남은 자리에는 자동으로 1이 들어갑니다.

i 가 0인 경우는 1로만 n 자리를 채운 경우이므로 1가지

i 가 1부터 n//2 인 경우는 각각 ${}_{n-i}{C}_i$가지입니다.

from math import comb

n=int(input())
print(sum([comb(n-i,i)%15746 for i in range(1, n//2 + 1)])+1)

 

그런데 위에서 언급한 것처럼 답을 구해보면 결과가 피보나치 수열이 나오는 거예요.

피보나치 수열 : 아래 성질을 만족하는 수열, 예) 1,1,2,3,5,8,13,21,34,55,...

$a_{n+1}=a_n+a_{n-1}$

 

n=1~9의 결과값: 1,2,3,5,8,13,21,34,55,...

그래서 피보나치 수열을 구했더니 맞았습니다!

def f(n):
    a, b = 1,1
    for _ in range(n):
        a, b = b, (a+b)%15746
    return a
print(f(int(input())))

 

위 피보나치 수열의 관계식을 행렬로 정리하면

 

$\left[\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}{a}_{n-1}\\ a_{n-2}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]$

>>> $\left[\begin{array}{cc}{a}_{n+1}& a_n\\ a_n& a_{n-1}\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n$

 

>>> 카시니 항등식: $det\left[\begin{array}{cc}{a}_{n+1}& a_n\\ a_n& a_{n-1}\end{array}\right]=det{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=(det\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]{)}^n=(-1{)}^n$

 

A : 정방행렬$($Square Matrix$)$  >>> $A^{m+n}=A^m\cdot A^n$

 

>>> ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{m+n}={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\cdot {\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n$

 

>>> $\left[\begin{array}{cc}{a}_{m+n+1}& a_{m+n}\\ a_{m+n}& a_{m+n-1}\end{array}\right]=\left[\begin{array}{cc}{a}_{m+1}& a_m\\ a_m& a_{m-1}\end{array}\right]\cdot \left[\begin{array}{cc}{a}_{n+1}& a_n\\ a_n& a_{n-1}\end{array}\right]$

 

위 행렬식을 활용한 코드

def f(n, p):
    if n == 1:
        return [[1, 1], [1, 0]]
    M = f(n//2, p)
    a, b, c, d = M[0][0], M[0][1], M[1][0], M[1][1]
    M[0][0] = (pow(a, 2, p) + b*c%p) % p
    M[0][1] = b*((a+d)%p)%p
    M[1][0] = c*((a+d)%p)%p
    M[1][1] = (pow(d, 2, p) + b*c%p) % p
    if n%2: 
        return [[(M[0][0] + M[0][1]) % p, M[0][0]], [(M[1][0] + M[1][1]) % p, M[1][0]]]
    else:
        return M

p = 15746
n = int(input())
print(f(n+1, p)[0][1])

 

위 행렬식에서 구할 수 있는 도가뉴 항등식을 활용하면 m=n 일 때, 2n$($짝수$)$항 m=n-1일 때, 2n-1$($홀수$)$항의 피보나치 수열을 n항의 피보나치 수열정도 까지만 연산해서 얻어 낼 수 있습니다.

 

도가뉴 항등식 : $a_{m+n}=a_{m-1}\times a_n+a_m\times a_{n+1}$

짝수항 : $a_{2n}=a_{n-1}\times a_n+a_n\times a_{n+1}=a_n\times (a_{n-1}+a_{n+1})=(a_{n+1}{)}^2-(a_{n-1}{)}^2$
홀수항 : $a_{2n-1}=a_{n-1}\times a_{n-1}+a_n\times a_n=(a_n{)}^2+(a_{n-1}{)}^2$

 

def f(n,p):
    a, b = 1,1
    for _ in range(n//2-1):
        a, b = b, (a+b)%p
    if n % 2:
        return (pow(b,2)+pow(a,2)) % p
    else:
        return (pow(b,2)-pow(b-a,2)) % p

#원래 피보나치 수열은 1,1,2...로 시작하는데 이 문제의 답은 1,2로 나오기 때문에 1을 더했습니다.
n = int(input()) + 1 
print(f(n, 15746))

 

예제 입력 1 

4

예제 출력 1 

5