[programmers/py] 2 x n 타일링

2 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12900

문제 설명

• 가로=2, 세로=1일 타일을 사용해 2 X N 직사각형을 채우는 방법의 수를 return

문제 풀이

• DFS를 통해 접근하면 시간초과
• 각 N에 따른 값을 적어보면 피보나치 수열이 나옴

def solution(n):
    x = 1
    y = 2
    
    if n==1:
        return x
    if n==2:
        return y
    
    for i in range(n-2):
        temp=x
        x=y
        y=x+temp
        
    answer=y%1000000007
    
    return answer
    
### 다른 사람 풀이
# a,b=1,1
# for i in range(n):a,b=b,a+b
# return a%100000