[파이썬] 소프티어 지도 자동 구축

Softeer

• 사이트에서 문제를 확인해주세요.

나의 풀이

소프티어

반복이 진행될 수록 작은 지도를 반으로 가르는 직선들이 계속 추가 된다.

따라서 n번 째 시행 때 한 변에 놓인 점의 개수는 다음과 같다.

$a_n = 2 + \sum_1^{n}2^{n-1}$

import sys

n = int(input())
length = 2
for i in range(n):
    length += (2 ** i)
print(length ** 2)

 

다른 사람 풀이

반으로 나누면서 중간에 겹치는 점이 발생하기 때문에 1을 빼준다.

import sys

N = int(sys.stdin.readline())
dp = [0] * 16 # N의 최댓값은 15이기 때문에 0단계 ~ 15단계 총 16개 칸 생성
dp[0] = 2 # Start 지점의 한변의 점의 개수 = 2

# N번째 단계의 한 변의 점의 개수는 (N-1번째 점의 개수 + N-1번째 점의 개수-1) 과 같다
for i in range(1,N+1):
    dp[i] = dp[i-1] + (dp[i-1] -1) 

# print(dp) -> 각 단계에서 한 변의 점의 개수
print(dp[N]**2) # 총 점의 개수 = 한 변의 점 개수의 제곱

[Softeer/Python] 지도 자동 구축 ★★☆☆☆ - 효과는 굉장했다!