[Softeer / Level2] 지도 자동 구축

 

https://www.softeer.ai/practice/info.do?idx=1&eid=413 

Softeer

---

 

전체 격자의 갯수가 4 -> 9 -> 25 ... 제곱으로 늘어나서 격자점의 갯수만 알면 해결할 수 있다.

 

점화식의 규칙만 알아내면 되는데, 내가 생각했을 때 (이전 격자 갯수 + 올림(이전 격자 갯수 / 2)) 하면 될 줄 알았는데 아니였다..

처음 생각한 점화식

해답풀이는 아래처럼 (이전격자 + 2 ^ (i - 1)) 로 구성된다.

1단계 : (2+1) ^ 2

2단계 : (3+2) ^ 2

3단계 : (5+4) ^ 2

4단계 : (9+8) ^ 2

...

<내 코드>

import sys

N = int(sys.stdin.readline())
S = [0] * 16

S[0] = 2
for i in range(1, 16):
    S[i] = S[i-1] + (2**(i-1))


print(S[N] ** 2)

 

dp는 난이도를 막론하고 점화식을 찾는 과정이 전부인데 그 과정이 난해하다