[프로그래머스/Lv.2] 2 x n 타일링 | 파이썬

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12900

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

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

 

입출력 예

다음과 같이 5가지 방법이 있다.

 

나의 풀이 (실패)

import sys
sys.setrecursionlimit(10**6)

def DFS(n):
    global answer
    
    if sum(arr) >= n:
        if sum(arr) == n:
            answer += 1
        return
    
    for i in [1, 2]:
        arr.append(i)
        DFS(n)
        arr.pop()

def solution(n):
    global arr, answer
    arr = []
    answer = 0
    
    DFS(n)

    return answer % 10000000007

재귀 함수로 풀어봤는데 역시나 시간 초과로 실패했다.

 

다른 사람의 풀이

def solution(n):
    dp = [0] * n
    dp[0], dp[1] = 1, 2
    
    for i in range(2, n):
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    
    return dp[n-1]

`dp[n] = dp[n-1] + dp[n-2]`이라는 점화식을 만들어서 동적계획법으로 풀었다.

 

`dp[n]`을 완성하는 방법은 두 가지가 있다.

1. `dp[n-1]`에 세로 타일을 1개 추가해서 한 칸을 채운다.
2. `dp[n-2]`에 위아래로 가로 타일 2개를 추가해서 2칸을 채운다.

 

예를 들어 `dp[4]`의 경우에 타일의 경우의 수는 다음과 같다.

• n=2: 11, 2 → 112, 22 (가로 타일 2개 추가)
• n=3: 111, 21, 12 → 1111, 211, 121 (세로 타일 1개 추가)
• n=4: 1111, 211, 112, 121, 22 → 2 + 3 = 5가지