프로그래머스 - 3xn 타일링 풀이 (python3)

프로그래머스 3xn 타일링의 문제 설명은 여기서 볼 수 있고 풀어볼 수도 있다.

 

이전에 2xn 타일링 문제를 풀어봤기 때문에 3n 타일링 문제에 도전해보았다.

원리는 비슷하고 조금 응용하면 되겠지.. 하고 쉽게 생각했지만 생각보다 그 응용이 쉽지 않았다..

3xn 타일링도 2xn 타일링과 마찬가지로 DP로 풀 수 있는 문제였다.

 

문제 풀이를 시작하면, n이 홀수일 경우에는 크기가 2인 타일을 채울 수 없기 때문에 n이 짝수인 경우만 생각한다.

먼저 n=2인 경우 3가지 경우의 타일 모양이 나오고, 그 다음 단계로 진행할 때마다 아래와 같이 매번 2개씩 새로운 모양의 타일이 생긴다.

 

 

f(n) = 가로의 길이가 n인 타일을 채울 수 있는 경우의 수 라고 하자.

 

n = 4일 때는 이전 단계(n=2)에서 2칸이 추가 되었으므로

f(4) = (이전 단계의 경우의 수) x (n = 2일 때 경우의 수) + 2        
       = f(2) x 3 + 2 = 11

임을 알 수 있다.

 

n = 6일 때도 마찬가지로 이전 단계(n=4)에서 2칸이 추가되었으므로

f(6) = f(4) x 3 + 2 이라고 생각할 수 있는데, 여기에는 빠진 모양이 있다.

아래 그림을 보면 n=4일 때 나온 특수 경우가 추가되는 경우를 생각해야 한다. 이 모양은 뒤에 붙을 수도 있고 앞에 붙을 수도 있기 때문에 x2를 해 주는 것이다.

즉, f(6) = f(4) x 3 + f(2) x 2 + 2 = 41 이다.

 

그렇다면 n = 8인 경우에는 f(8) = f(6) x 3 + f(4) x 2 + f(2) x 2 + 2 = 153이다.

 

이를 통해 규칙성을 찾아보면 f(n) = f(n-2) x 3 + f(n-4) x 2 + … + f(2) x 2 + 2 라는 점화식을 얻을 수 있다.

n을 짝수로만 가정하면 f(n) = f(n-1) x 3 + f(n-2) x 2 + … + f(2) x 2 + 2 라는 점화식으로도 풀 수 있다.

 

위 점화식을 적용한 문제 풀이 코드는 다음과 같다.

def solution(n):
    answer = [0,3,11]
    index = int(n/2)
    if n % 2 != 0: return 0
    if index < 3: return answer[index]

    for i in range(3, index+1):
    	# answer[i:j] -> answer에서 index가 i인 원소부터 j-1인 원소까지의 sub-array
        answer.append((3*answer[i-1]+sum(answer[1:i-1])*2+2)%1000000007)

    return answer[index]