[소프티어 softeer] 지도 자동 구축(Lv.2) - 파이썬(Python)

문제

https://softeer.ai/practice/6280

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

 

풀이

문제를 보자마자 왠지 모르게 DP 문제라는 감이 와서 점화식을 세우기 위해 패턴을 찾았습니다.

찾은 규칙

literation	추가된 점 개수	점 한줄에 개수	총 점 개수
0	0	2	4
1	1	3	9
2	2	5	25
3	4	9	81
4	8	17	289

 

1 literation 까지 리스트에 초기값으로 너어줍니다.

점이 *2 규칙으로 추가되고, 점 한줄에 개수는 추가된 점 개수+ 그전에 점한줄에 개수입니다.

그리고 점 한줄에 개수를 제곱하면 총 점 개수가 나옵니다.

규칙

 

규칙 적용한 코드

import sys

input = sys.stdin.readline

n = int(input())

addLines = [0] * 16
addLines[0] = 0
addLines[1] = 1

answer = [0] * 16
answer[0] = 2
answer[1] = 3


for i in range(2, n+1):
    addLines[i] = addLines[i - 1] * 2
    answer[i] = answer[i - 1] + addLines[i]


print(answer[n]*answer[n])