[Programmers]Lv 4. 3xn 타일링

문제:

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

  *타일을 가로로 배치하는 경우

  *타일을 세로로 배치하는 경우

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

풀이 방법:

 이전 단계인 2xn 타일링과 같이 동적계획법을 사용해서 풀어야 하는 문제이다. n이 증가할 때마다 어떠한 규칙에 따라서 증가하는지 파악할 수 있다면 쉽게 문제를 풀 수 있다. n이 6~8까지 그려보면 대충 규칙을 찾아낼수 있다. 우선 n이 홀수 일 때는 타일링을 할 수 없다. 따라서 이 경우에는 항상 0이다.

그리고 타일로 만들 수 있는 모양이 한정적이라서 그 모양들을 여러 개 붙인 모양으로 반복이 된다. 규칙이 있는 타일은 다음과 같다.

 이 타일들의 조합으로 반복이 되며 n=4일 때부터는 추가적인 몇개의 조합이 더 생기게 된다. 이는 이전 n(짝수만 생각했을 때)과 연관이 있기 때문에 다음과 같이 코드를 짤 수 있다.

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

문제 링크:

https://programmers.co.kr/learn/courses/30/lessons/12902