[Python] 11726 2*n 타일링

👉 11726 2 x n 타일링

[정답 코드]

import sys

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

n = int(sys.stdin.readline())
print(tiling(n))

[풀이]

• 1 x 2 타일이 두개가 쌓여있는 것을 2로 두고, 2 x 1 타일 하나를 1로 두면 n을 1과 2의 합으로 표현하는 것으로 생각할 수 있다.

[적용 알고리즘]

• Dynamic Programming