[백준 2903번 파이썬]'중앙이동 알고리즘' 모든 풀이 비교 분석

안녕하세요!

Wooji입니다.

오늘은 백준 2903번 중앙 이동 알고리즘을 풀어보았습니다.

 

배경지식

이 문제는 배경지식이라고는 필요 없고 규칙을 어떻게 간단하게 찾느냐가 관건입니다.

논리 및 아이디어

• 단순히 문제를 풀기 전 논리일 뿐입니다. 틀릴 확률이 다분합니다.

1. N 단계에서 N-1 단계의 점은 영향을 주지 않으므로 그대로 더하면 되겠다.
2. 한 단계가 더해질 때마다 사각형 하나에 점이 5개씩 생긴다.
3. 겹치는 점은 N단계에서 (2^(N-1))× (2^(N))×2 개다.
4. 최종 식은 [(N-1) 단계의 점의 개수] + 5 × (4^N) - (2^(N-1))× (2^(N))×2

나의 코드

num=int(input())
new=4
for i in range(num):
    new=new+5*4**(i)-(2**(i)-1)*(2**(i))*2
print(new)

규칙을 찾아서 피보나치수열처럼 코드를 짜주었는데... 현실은 더 쉬운 규칙이 있었다는 것..

 

최적의 코드

이번 문제의 최적의 코드는 다른 분의 블로그를  참조했습니다. 출처는 맨 아래에 남겨놓겠습니다. 

N = int(input())
print((2**N+1)**2)

더 쉬운 규칙으로는 (한 변의 점의 개수)의 제곱

그리고  한 변의 점의 개수는 2,3,5,9,17로 커졌고, 1,2,4,8 만큼씩 더해진 것.

 

 

배운 점 및 보완할 점

• 쉬운 규칙을 찾도록 노력하자.... 예제에서 9,25를 본 순간 제곱수라는 것을 떠올렸다면,,,

 

출처

 

백준 2903번 중앙 이동 알고리즘 파이썬