2022.06.05 [프로그래머스] (python 파이썬) 3Xn 타일링

 

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

코딩테스트 연습 - 3 x n 타일링

 

---

풀이

이 문제는 우선 규칙을 찾아야한다.

먼저 n이 홀수면 전체 칸이 홀수가 되기 때문에 2X1의 타일로 채울 수 없기 때문에 0을 리턴해준다.

n=2일 때, 3

n=4일 때, 11

n=6일 때, 41

손으로 그려보다 보면 이런식으로 증가하는것을 확인할 수 있다.

여기서 점화식을 찾아야하는데 

그림 출처 : https://s2choco.tistory.com/24

위의 그림에서 보면 n이 8일 때, 이전 짝수의 *3, 그 이전의 값들*2 +2란 규칙이 있다. 

왜냐하면 2씩 증가할때마다 2칸씩 나누면 한칸에 놓을 수 있는 경우의 수=3

그래서 이전의 값에서 *3을 해야하고 그 이전의 값은 상하 반전을 할 경우도 생각해야하기 때문에 *2

그리고 해당 n에 대해 새로운 경우 2개가 나오기 때문에 

f(n)=f(n-1)*3+f(n-2)*2+f(n-3)*2......+2란 점화식이 나온다.

def solution(n):
    arr=[0]*2501
    arr[1]=3
    if n%2==1:
        return 0
    for i in range(2,n//2+1):
        arr[i]=((arr[i-1]*3+sum(arr[:i-1])*2+2)%1000000007)
    return arr[n//2]