[프로그래머스] 2xn 타일링

문제

• 세로 길이가 2이고 가로 길이가 n인 바닥을 가득 채우려고 합니다.
  • 타일을 가로로 배치하는 경우
  • 타일을 세로로 배치하는 경우
• 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 60,000 이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,0007으로 나눈 나머지를 return 해주세요.

풀이

DP

파이썬으로 풀이하는 경우 recusion limit 에러가 발생할 수 있습니다.

import sys
sys.setrecursionlimit(100000)

코드

import sys
sys.setrecursionlimit(100000)

DIV = 1000000007
cache = None
def solution(n):
    global cache # 남은 길이에서의 cache 저장
    cache = [0] * (n+2)
    return solve(n)

# extraLength: 남은 길이
def solve(extraLength):
    global cache, DIV
    if extraLength == 0:
        return 1
    elif extraLength < 0:
        return 0
    elif cache[extraLength] != 0:
        return cache[extraLength]
    
    result = solve(extraLength - 1) # 세로
    result += solve(extraLength - 2) # 가로
    cache[extraLength] = result % DIV 
    return cache[extraLength]