Softeer: 지도 자동 구축 Python

 

 

문제의 입력 조건이 1 이상 15 이하인 것으로 봐서 DP나 Memoization을 사용해야 한다.

나는 dp가 너무 어렵기 때문에 memoization을 썼다.

이 문제에는 규칙이 있는데, 처음에는 한 변의 점 개수가 2개, 그 다음에는 3개, 그 다음에는 5, 9, 17, ... 이렇게 된다.

여기서 보면 (다음 단계의 한 변의 점 개수)  = (직전 단계의 한 변의 점 개수) * 2 - 1이다.

그리고 전체 개수는 (한 변의 점 개수)^2이다.

따라서 아래와 같이 코드를 짰고 테스트케이스 모두 만족했다.

import sys

N = int(input())    # 단계

start = 2
memo = [0] * (16)   # 0 ~ 15
memo[0] = 2

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

print(memo[N] ** 2)