[Softeer 연습문제] Lv2. 지도 자동 구축 (python)

[Softeer 연습문제] Lv2. 지도 자동 구축

문제확인 : https://softeer.ai/practice/6280

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

🔍 과정

1. 0단계 : 점 4개 / 1단계 : 점 9개 / 2단계 : 점 25개 / 3단계 : 점 49개
2. 한 변에 존재하는 점의 개수의 제곱이 전체 점의 개수임.
3. 한 변에 존재하는 점의 개수 : 2, 3, 5, 9, 17, 33 ....
4. N번째 단계의 한 변의 점의 개수는 (N-1번째 점의 개수 + N-1번째 점의 개수-1) 

 

 

💡 나의 풀이

import sys

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

# 한 변에 존재하는 점의 개수를 저장할 배열 dp 초기화
dp = [0] * 16 # 1<=N<=15 0단계 ~ 15단계 총 16개 칸
dp[0] = 2 # start 지점의 한 변에 있는 점의 개수

for i in range(1, N+1):
    dp[i] = dp[i-1] + (dp[i-1]-1)

print(dp[N]**2)