문제출처 : 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):
if n % 10 == 0:
if n == 10:
return 1
elif n == 20:
return 3
else:
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}')