알고리즘💻/DP
BOJ 13301번: 타일 장식물
호프
2021. 5. 5. 02:44
13301번: 타일 장식물
대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개
www.acmicpc.net
문제풀이:
기본적인 dp 활용 문제인 것 같다.
dp[1] = 1, dp[2] = 1로 초기화하고 (편하게 하기 위해 인덱스를 1부터 시작했다.)
dp[i] = dp[i-1] + dp[i-2]로 구했다.
dp를 구하면서 동시에 둘레의 길이도 구했다.
import sys
N = int(sys.stdin.readline())
dp = [0]*81
length = [0]*81
dp[1] = 1
dp[2] = 1
length[1] = 4
length[2] = 6
for i in range(3,N+1):
dp[i] = dp[i-1] + dp[i-2]
length[i] = (dp[i-1]+2*dp[i])*2
print(length[N])