종이: 10x20짜리, 20x20짜리
10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오.
10≤N≤300, N은 10의 배수
코드DP로 풀이
DP를 처음 활용해봤다. DP에 대한 자세한 사항은 따로 포스팅
def paper_recur(n):
if n == 1:
return 1
elif n == 2:
return 3
for i in range(3, n+1):
paper = arr[i-1] + 2*arr[i-2]
arr.append(paper)
return arr[n]
for tc in range(1, int(input()) + 1):
N = int(input())
n = N//10
arr = [0, 1, 3]
cnt = paper_recur(n)
print('#{} {}'.format(tc, cnt))
https://velog.io/@moong3871/DP-%EC%9E%AC%EA%B7%80-%EB%B0%8F-top-down-bottom-up-%EB%B9%84%EA%B5%90