[백준 1904 파이썬] 01타일

# 1. Fibonacci
# 2. Memory를 고려해서 list를 생성 x
# 3. Python3 시간초과 PyPy : 7440 ms
 
 
def solution():
    N = int(input())
 
    # 1 --> 1
    # 00 11 --> 2
    # 001 100 110 --> 3
    # 0000 1100 1111 0011  100 -->  5
 
    start = 1
    end = 2
    next = 0
    for i in range(2, N):
        next = start + end
        start = end
        end = next
 
    return next
 
print(solution()%15746)