[SWEA] 4869 [파이썬 S/W 문제해결 기본] 4일차 - 종이붙이기 / 파이썬(python)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

# 문제 링크

swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

SW Expert Academy

 

# Soultion

점화식을 찾기위해 필요한 영역들을 구해보았다.

1,3,5,11,21... 과 같은 순서로 진행되었는데, 자세히보면 f(n) = f(n-1)+f(n-1)*2 와 같이 진행된다는 사실을 알 수 있다.

따라서 중복된 값을 이중으로 계산하지않도록 for문을 이용하여 li에 저장하는 방식으로 진행하여 마지막에 출력해주었다.

t = int(input())
 
for tc in range(1,t+1):
    n=  int(input()) # 20xN 10의배수
    
    li = [0,1,3]
    
    for i in range(3,n//10+1):
        li.append(li[i-1] + li[i-2]*2)
    
    print("#"+str(tc),li[-1])