[알고리즘] 프로그래머스 3 x n 타일링

문제 설명

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

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우
  예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.
  
  직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한 사항

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

입출력 예

n	result
4	11

풀이

딱 봐도 전에 쌓인 타일에서 어떻게 더 쌓아서 반복해가는 dp 문제이다.
일단 n이 홀수인 경우엔 절대 타일을 만들 수 없다. 각 타일의 크기는 2인데, 만들어야할 너비는 3 x 홀수 = 홀수이기 때문이다.
따라서 dp를 전부 0으로 초기화해주자.

먼저 3*2 타일링을 하는 경우는 세 가지 이다.

그럼 3*4를 타일링 하려면, 3*2를 두 번 이어 붙인다. 이때 예외가 있다.


이렇게 ㄱ자와 ㄴ자 모양으로 둘러쌓인 경우도 있다.
따라서 3*3(3*2 타일링하는 경우의 수) + 2(ㄱ과 ㄴ으로 둘러쌓인 모양) = 11이다.

다음으로 3*6을 타일링해보자.3*4와 마찬가지로, 3*4 뒤에 3*2를 이어 붙인다. 그럼 11*3=33가지가 나올 것이다.

이때 4에서 고려한 이상한 모양을 다시 생각해줘야 한다.
3*6으로도 저 이상한 모양 두 가지를 만들 수 있다. |---|, |___| 이렇게 두 가지이다.

또, 3*2 뒤에 3*4인 이상한 모양 |--|, |__|를 또 이어 붙일 수 있다.

즉, n=4부터 생기는 이상한 모양 두 가지를 계속 이어 붙일 수 있다.

정리하자면

1. 3*(i-2) 타일 뒤에 3*2(3가지)타일을 이어 붙인다.
2. 3*(i-4)타일 뒤에 3*4(2가지) 이상한 모양 타일을 이어 붙인다.
   3*(i-6)타일 뒤에 3*6(2가지) 이상한 모양 타일을 이어 붙인다.
   ...
   3*i(2가지) 이상한 모양 타일을 이어 붙인다.
   이렇게 된다.

코드

def solution(n):
    answer = 0
    dp = [0] * (n+1)
    dp[0] = 1
    
    for i in range(2, n+1, 2) :
        # 3*(i-2)타일에 3*2 타일을 이어 붙임
        dp[i] = (dp[i-2] * 3)
        
        # dp[i-4], dp[i-6], ...dp[0] 타일에 |___| or |----| 타일을 이어 붙임.
        for j in range(4, i+1, 2) : 
            dp[i] += (dp[i-j] * 2)
            
    answer = dp[n]%1000000007
    return answer

의문이 드는 점, 개선해야할 점은 댓글로 남겨주세요.
감사합니다 😽