[BOJ] 1904 - 01타일 (Python)

 

 

아이디어

 

만들 수 있는 2진 수열 개수의 규칙을 찾는다.

 

 

풀이 #1

 

만들 수 있는 2진 수열은 타일 개수에 따라 피보나치 수열을 이루고 있다.

res와 prev에 각각 현재와 이전 피보나치 수 저장하여 계산하고, res를 15,746으로 나눈 나머지를 출력한다.

 

def solution():
    N = int(input())
    prev = res = 1
    for i in range(2, N+1):
        res, prev = (res+prev)%15746, res
    print(res)

solution()

 

 

 

풀이 #2

 

행렬 곱을 이용하여 피보나치 수열을 빠르게 구할 수 있다.

2차원 행렬을 1차원 튜플로 표현하고, N을 이루는 2의 제곱수마다 해당하는 거듭제곱 행렬을 곱한다.

 

def fibo(a, b):
    return ((a[0]*b[0]+a[1]*b[2])%15746,
            (a[0]*b[1]+a[1]*b[3])%15746,
            (a[2]*b[0]+a[3]*b[2])%15746,
            (a[2]*b[1]+a[3]*b[3])%15746)

N = int(input())
F = (1, 1, 1, 0)
res = (1, 1, 1, 0)
while N:
    if N&1:
        res = fibo(F, res)
    N >>= 1
    F = fibo(F, F)
print(res[1])