-
(스택) 종이붙이기개발노트 2020. 2. 19. 16:10
이 문제의 저작권은 SW Expert 아카데미에 있습니다.
문제는 위 링크에서 확인할 수 있습니다.
def f(n): #점화식을 잘 세울 필요가 있다. #마지막 경우만 따져본다. #20*20 종이가 하나 #20*10 종이가 하나 #10*20 종이 둘 if n < 2: return 1 return f( n-1 ) + 2 * f( n-2 ) for t in range(int(input())): N = int(input()) // 10 print(f"#{t+1} {f(N)}")
가로 30인 종이를 만든다고 할 때
20*20 종이와 10*20 종이를 사용할 수 있습니다.
10*20 종이는 돌려서 사용이 가능하기 때문에 20*10으로 사용할 수도 있습니다.
피보나치수열과 비슷하기 때문에 점화식을 이용해서 문제를 풀어봤습니다.
마지막 경우만 따져봤을 때
#20*20 종이가 하나
#20*10 종이가 하나
#10*20 종이 둘f(n-1) + 2 * f(n-1)과 같은 식을 만들었습니다.