[Python] 백준 11726 2Xn 타일링

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

11726번: 2×n 타일링

문제해결

- 세로 길이는 2로 고정이라는 것에 주목하자. 

2가지 배열중 하나로 놓게 된다.

그러면 가로길이가 1인 1번으로 한개 놓던가 가로길이가 2인 2번으로 2개 놓는 방법이 있다. 이를 보면 피보나치 수열

fib(n) = fib(n-1) + fib(n-2) 가 생각이 난다.

CODE

import sys
input = sys.stdin.readline

def fib(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    return fib(n-1) + fib(n-2)
if __name__=="__main__":
    n = int(input())
    ans =fib(n)%10007
    print(ans)

 결과는 시간초과!

= 재귀를 사용하기는 시간복잡도가 너무 크다는 뜻이다.

 

그러면 생각나는 것이 리스트에 숫자를 append해서 for문으로 O(N) 시간복잡도로 끝내는 방법이 있다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
F = [0,1,2]
for i in range(3,1001):
    F.append(F[i-1] + F[i-2])
print(F[n]%10007)