Baekjoon 11726번 2xn 타일링

문제

https://www.acmicpc.net/problem/11726

걸린 시간

00 : 37 : 09

풀이

Python3

import sys

def recu(n):
    if n in dic:
        return dic[n]

    if n == 0:
        dic[n] = 1     
        return 1
    elif n < 0:
        return 0
    else:
        dic[n] = recu(n-1) + recu(n-2)
        return dic[n]

if __name__ == "__main__":
    sys.setrecursionlimit(1003)
    n = int(input())    

    visited = [0] * 1001
    dic = {}

    print(recu(n)%10007)

피보나치 수열 문제와 똑같다.

메모이제이션을 사용하지 않았을 때 복잡도는 O(2ⁿ)으로 문제의 최대입력인 1000에 가까운 수가 들어온다면 영원히 끝나지 않을 것 같다.

중복을 제거하면 O(n)의 복잡도를 갖게 된다.