백준 2903번 풀이

문제

https://www.acmicpc.net/problem/2903

2903번: 중앙 이동 알고리즘

세줄요약이 안된다... 그냥 가서 보자. 

 

풀이

일단 이 문제를 처음 본 본인의 심정:

뭐라는겨...

 

솔직히 패턴 파악해야되는데 1, 2 다음에 뜬금없이 5가 나오면 어쩔 수 없다. 손으로 그려봐야지. 그래서 그렸습니다.

이렇게 봐도 모르겠다면 정상이다. 나도 1089가 제곱수인가 해서 울프램알파에 루트 때려보고 알았음. 하지만 여기에는 마치 히든보스마냥 숨겨진 패턴이 있다면 믿겨지는가? 에이 뭔 dog sound냐고? 아 일단 들어봐요.

 

굵은 글자를 잘 보자. 1을 넣으면 9가 나오는데 이건 3의 제곱이고 3은 2+1이다. 그리고 2를 넣으면 나오는 25는 5의 제곱이고 5는 2+1+2이다. 3을 넣으면 나오는 81은 9의 제곱이고 9는 2+1+2+4이다. 어? 이거 완전 등비수열? 그렇다. 초항이 1이고 공비가 2인 등비수열의 '합'을 2에 더한 다음 그걸 제곱하면 된다.

 

import sys

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

Sooyeol = (2 ** N - 1) / 1 # 등비수열의 합 Sn = a(r^n-1)/(r-1), 초항이 1이고 공비가 2인 등비수열
geom = (2 + Sooyeol) ** 2
print(int(geom))

이거 노션에 정리한것도 패턴찾고 주저리하는게 팔할이었음... 0은 고려 안해도 됩니다 어차피 입력값 1부터임.