[SWEA 5255][Python] [파이썬 S/W 문제해결 최적화] 2일차 - 타일 붙이기

코드

## SWEA 5255
T = int(input())
for test_case in range(1 ,T+1):
    N = int(input())
    arry = [-1]*(N+1)
    for i in range(1,N+1):
        if i == 1 :
            arry[i] = 1
        elif i == 2 :
            arry[i] = 3
        elif i == 3 :
            arry[i] =  6
        else :
            arry[i] = arry[i-1] + 2*arry[i-2] + arry[i-3]

    print(f"#{test_case} {arry[N]}")

 

풀이

상향식 방법으로 점화식을 찾는게 어려웠다. 

arry[N]을 만드는 방법은 반복을 제외하고 3가지가 있는데,

1) arry[N-1]일 경우 : 2x1 타일 하나를 새로로 붙인다. 

2) arry[N-2]일 경우 : 2x1 타일 두개를 가로로 붙인다. or  2x2 타일 하나를 붙인다.

   → 2x1타일 두개를 새로로 붙이면 1)의 경우의 수와 중복이 일어난다. 

3) arry[N-3]일 경우 :  2x3 타일 하나를 붙인다. 

위 경우를 제외하고 모두 반복이므로 점화식을 만들 수 있다.