백준-11726 : 2×n 타일링

문제

풀이

먼저 재귀함수로 풀면 파이썬 내부에서 재귀함수 호출 스택을 초과하여 런타임 에러가 발생한다.

leng = int(input())

def tile(leng):
    if leng == 1 or leng==2:
        return leng
    elif leng > 2:
        return tile(leng-1)+tile(leng-2) %10007

print(tile(leng))

Memoization으로 구현하면 된다.

leng = int(input())

memo = [0]*(leng)
memo[0:2] = [1,2]

for i in range(2, leng):
    memo[i] = (memo[i-1]+memo[i-2])

print(memo[leng-1]%10007)