[백준] 11726 2xn 타일 Python

1. 문제

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는
방법의 수를 구하는 프로그램을 작성하시오

 

2. 요구사항

시간 제한 1초

메모리 제한 256 MB

1 <= n <= 1,000

3. 알고리즘 분류

* 다이나믹 프로그래밍

4. 접근 방식

이것도 n = 7 까지 모든 경우의 수를 계산해 봤는데 아니나 다를까 피보나치였고

n= 1 는 1, n = 2 는 2 를 초기값으로, n = 3 이상은 n-1 과 n-2 합으로 계산했다

4. 코드 구현

# 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 
# 10,007 로 나눈 나머지를 출력한다 
# 1 <=n <= 1,000

def rect(n):
    list = [0] * (n+1) # 결과 정리 
    if n <= 1: # 기저 설정
        return n
    list[1] = 1
    list[2] = 2
    
    # list[2] 는 2 니까, for 문은 3부터 
    for i in range(3, n+1):
        list[i] = (list[i-1] + list[i-2]) % 10007
        
    result = list[n]

    return result 

if __name__ == '__main__':
    n = int(input())
    print(rect(n))