[Python | 백준] 11726번: 2×n 타일링

2×n 크기의 직사각형을 채우는 방법의 수

 

n이 1일 때는 1, 

n이 2일 때는 가로 두개, 세로 두개로 2가지 ( =, || )

n이 3일 때는 n이 2일 때 + n이 1일 때

n이 4일 때는 n이 3일 때 + n이 2일 때

-> 점화식 : 직사각형 가로의 길이가 N인 경우는 n-1 경우의 수 + n-2 경우의 수를 더한 값

 

n = int(input())

def tiling(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
        
    return dp[n]

print(tiling(n))