문제
현대자동차그룹이 레벨3 자율주행차 상용화 목표에 발맞춰 총력을 다하고 있는 가운데, 국내 최고 수준의 지도 구축 기술력을 보유한 현대엠엔소프트는 자율주행에 필요한 정밀지도를 제작해 배포하고, 기술 고도화를 위한 연구에 매진하고 있다.
최근에는 도로 데이터를 기반으로 자동으로 정밀지도를 구축하는 ‘지도 자동 구축(Map Auto Creation, 이하 MAC)’ 기술을 개발해 지도 제작 시간을 단축하고 정밀도를 향상시키는 데 성공했다.
자율주행차용 정밀 지도에 관한 궁금증으로 인터넷 검색을 해보니, Diamond-Square-Algorithm이라는 것을 찾게 되었다. 이 알고리즘은 정사각형을 이루는 점 4개를 고르고 그 후에는 다음과 같은 과정을 거쳐 모양이 만들어진다.
정사각형의 각 변의 중앙에 점을 하나 추가한다.
정사각형의 중심에 점을 하나 추가한다.
[그림]은 0단계(start)에서 2단계(2 iterations)까지 수행한 결과이다. 각 단계(N)가 계속해서 커져갈수록 점의 수가 커져간다.
제약조건
1 ≤ N ≤ 15
입력형식
첫째 줄에 N이 주어진다.
출력형식
첫째 줄에 N단계를 거친 점의 개수를 출력한다.
입력예제1
1
출력예제1
9
코드
import sys
import math
input = sys.stdin.readline
result = 0
now = 1
n = int(input())
for i in range(n+1):
result = math.pow(now+1,2)
now = now*2
print(int(result))문제 이해
- 0단계(start)부터 시작, 정사각형 개수 1개, 점 개수 4개
- 정사각형마다 중심에 점 하나 추가
- n단계를 거쳤을 때의 점의 개수 출력
풀이
단계 | 정사각형개수 | 점개수 순이라고 할 때,
- 0단계 | 1 | 4
- 1단계 | 4 | 9
- 2단계 | 16| 25
- 3단계 | 64| 81
정사각형의 개수가 1의 2승, 2의 2승, 4의 2승, 8의 2승 ... 처럼 {(이전 단계 정사각형개수의 제곱근)*2의 제곱}으로 이루어진 것을 알 수 있다.
여기서 정사각형개수의 제곱근을 now라고 한다면,
정사각형의 개수는 (now)의 제곱, 점의 개수는 (now+1)의 제곱이 된다.
따라서 단계마다 점의 개수를 Result라고 할 때,
n+1번 동안(0단계가 있으므로) 아래 순서를 반복해주면 된다.
- result = math.pow(now+1,2)
- now = now*2
예를 들어 n=4라면,
-
0단계
(정사각형 개수의 제곱근) = now = 1
(정사각형 개수) = math.pow(now,2) = 1
(점의 개수) = result = math.pow(1+1,2) = 4 -
1단계
(정사각형 개수의 제곱근) = nowx2 = 1x2 = 2
(정사각형 개수) = math.pow(now,2) = math.pow(2,2) = 4
(점의 개수) = result = math.pow(2+1,2) = 9 -
2단계
(정사각형 개수의 제곱근) = nowx2 = 2x2 = 4
(정사각형 개수) = math.pow(now,2) = math.pow(4,2) = 16
(점의 개수) = result = math.pow(4+1,2) = 25 -
3단계
(정사각형 개수의 제곱근) = nowx2 = 4x2 = 8
(정사각형 개수) = math.pow(now,2) = math.pow(8,2) = 64
(점의 개수) = result = math.pow(8+1,2) = 81 -
4단계
(정사각형 개수의 제곱근) = nowx2 = 8x2 = 16
(정사각형 개수) = math.pow(now,2) = math.pow(16,2) = 256
(점의 개수) = result = math.pow(16+1,2) = 289
