(백준 알고리즘 문제풀이) 11727번 2xn 타일링 2

문제

문제 링크

 

문제 접근

• dp알고리즘과 일반화 공식 An을 구하는 것이 좋은 접근일 것이다
• A1 = 1, A2 = 3이라는 것을 미리 구해주는 것이 가장 좋다.
• 그리고 A3 = 5, A4 = 11이라는 점을 활용하여 피보나치 함수를 변형하여 An = A(n-2) + 2 * A(n-1)을 일반화해준다.
• 구하고자하는 An에 % 10007을 이용하여 결과를 도출한다.

코드

import sys
# 재귀 함수의 제한 범위를 늘려주는 방법
sys.setrecursionlimit(10**6)

num = int(sys.stdin.readline())
memo = dict()


def cal(N, dictionary):
    if N == 1:
        return 1
    elif N == 2:
        return 3
    else:
        if N not in dictionary:
            dictionary[N] = cal(N-1, dictionary) + 2 * cal(N-2, dictionary)
            return dictionary[N]
        else:
            return dictionary[N]


result = cal(num, memo) % 10007
print(result)

느낀점

재귀 함수와 dictionary 자료구조를 활용하여 메모리, 시간초과의 문제를 없애주고, 재귀함수의 제한 범위를 늘려줌으로써 문제를 해결하였다. 위 문제를 통하여 재귀함수의 제한 범위 확장 및 파이썬의 자료구조를 활용한 메모리를 보다 효율적으로 사용할 수 있다는 것을 많이 깨달았다.