(Python/🥉3)백준알고리즘 2903번: 중앙 이동 알고리즘

백준알고리즘 중앙 이동 알고리즘

 

문제:

상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. 외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다. 알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.

1. 정사각형의 각 변의 중앙에 점을 하나 추가한다.
2. 정사각형의 중심에 점을 하나 추가한다.

초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다. 아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.

문제

 

입력:

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 15)

출력:

첫째 줄에 과정을 N번 거친 후 점의 수를 출력한다.

 

import sys
N  = int(sys.stdin.readline())

dp = [0] * 17
dp[0] = 4
dp[1] = 9

for i in range(2, 17):
    dp[i] = (int((dp[i-1]** 0.5) + (2**(i-1))))**2
print(dp[N])

 

 

 

이번문제는 dp를 사용해 보았다 

규칙을 잘 찾아보니 

a2 = (2+2**0) **2

a3 = (2+2**0 +2**1) **2

a4 = (2+2**0 +2**1 + 2**2) **2 

 

이런식이다.

 

이거를 바텀업 방식으로 저장해주고 dp 결과값을 뽑아주면 된다.