SWEA 4869 종이붙이기

문제출처 : SW Expert Academy

문제소개

20x10(a) / 20x20(b)  
직사각형 종이를 맘껏 쓸수 있다고 할때, 

20 x n(입력값, 10의 배수)의 직사각형을  
만들 수 있는 경우의 수(num)를 구하시오.

패턴찾기

경우의 수 구하기 나오면.. 먼저  
피보나치 수열 같은 패턴이 있는지 확인.  
-> DP (동적계획법, 문제를 부분으로 쪼개기) 활용

직사각형 만드는 경우의 수 : 4방향(위,아래,앞,뒤) 고려
20x20 : a2x2, b1 -> 3
20x30 : a3, (a1,b1)x2, (a2,a1)x2 -> 5
20x40 : a4x3, (a2,b1)x6, b2x2 -> 11

코드구현

def count(n):  # 경우의 수 count 함수
    if n % 10 == 0:
        if n == 10:  # n = 10 이면 경우의 수는 1
            return 1
        elif n == 20:  # n = 20 이면 경우의 수 = 3
            return 3
        else:  # n이 30이면 5, 40이면 8, 50이면 13
            return count(n-10)+(2*count(n-20))
    else:
        print("10의 배수만 입력할 수 있어요.")


T = int(input())
for tc in range(1, 1+T):
    n = int(input())
    num = count(n)
    print(f'#{tc} {num}')