Lv3. 2 x n 타일링

# 문제 설명

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

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

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

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

# 제한 사항

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

# 입출력 예

입출력 예 설명

입출력 예 #1 다음과 같이 5가지 방법이 있다.

문제 해결 시 고려사항

• Dynamic Programming, 점화식을 이용한 문제해결

본 문제는 DP(점화식)를 이용하여 해결할 수 있다.

점화식을 구하기 위해 아래와 같이 각 경우들에 대해 살펴보자.

N = 1인 경우 : 1

N = 2인 경우 : 2

N = 3인 경우 : 3

N = 4인 경우 : 5

N = 5인 경우 : 8

위의 5가지만 보아도 대략적인 점화식이 그려진다. N이 3 이상인 경우부터는

N = M인 경우 : M-2인 경우 + M-1인 경우와 같은 점화식의 유도가 가능하다.

문제에서 주어진 입출력 예 설명의 그림을 보아도 입증이 가능하다.

N이 4인 경우는 N이 2인 경우와 N이 3인 경우의 합으로 구할 수 있는데. 아래와 같은 경우로 구분할 수 있다.

N이 2인 경우

N이 3인 경우

위와 같은 정보를 최종 정리하여 아래와 같이 작성하였다.

 tile = [0,1,2]
     for  i in range(3,n+1):
         tile.append(tile[i-2] % 1000000007 + tile[i-1] % 1000000007)
     return tile[n] % 1000000007

전체 코드

def solution(n):
    tile = [0,1,2]
    for  i in range(3,n+1):
        tile.append(tile[i-2] % 1000000007 + tile[i-1] % 1000000007)
    return tile[n] % 1000000007