(스택) 종이붙이기
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)과 같은 식을 만들었습니다.