[프로그래머스/Python] 3 x n 타일링

문제 정보

제목 : 3 x n 타일링

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

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

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

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

 

제한 사항

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

입출력 예

n	result
4	11

 

입출력 예 설명

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

---

나의 풀이

dp에 n + 1까지 0으로 초기화한 리스트를 생성합니다. 초기값으로 dp[2]에는 3을, dp[4]에는 11을 저장합니다.

for루프를 이용해 4부터 n+1까지 2씩 증가하면서 dp에 값을 채우는데 여기서 식을 구하는게 어려웠습니다.

먼저 규칙을 찾아보면

n=2일 때는 이렇게 3개의 조합이 나올 수 있습니다.

n=4라면, n=2의 조합을 섞어서 만든 9개(3개*3개)와 새롭게 추가되는 패턴 2개가 나오게 됩니다.

 

n 크기의 도형은 n-2크기의 도형에 n=2 크기의 3개를 오른쪽에 붙여서 만들수있습니다. ( f(n-2) * 3 )

그리고 n이하의 특정 x사이즈 모양의 상자에 대해, 그 왼쪽에 n - x 크기 도형을 붙이는 형태가 만들어집니다.

 

 

이것을 점화식으로 풀어서 작성하면 이렇게 됩니다. 이것을 이용해 문제를 풀었습니다.

f(n) = f(n-2)*3 + f(n-4)*2 + f(n-6)*2 + . . . +  f(2)*2 + 2

 

코드

def solution(n):
    answer = 0
    dp = [0] * (n+1)
    dp[2] = 3
    dp[4] = 11
    
    for i in range(4,n+1,2) : # 4부터 n+1까지 2씩 증가함
        dp[i] = ((dp[i-2] * 3) + (sum(dp[:i-2]*2)) + 2) % 1000000007
    answer = dp[n]
    
    return answer