07. Python(중앙 이동 알고리즘)

[toc]

중앙 이동 알고리즘

문제

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

---

제출

N = int(input())
a = 2
b = 1
for i in range(N):
    a += b
    b *= 2
print(a**2)

1
9

2
25

3
81

4
289

5
1089

---

인사이트

• 알고리즘 문제 해결에 있어, 먼저 규칙을 찾는 것이 중요함을 인지하고 문제를 풀었음.

• 처음 ‘정사각형의 점 개수를 구하라’는 문제에서, 사실상 넓이를 구하는 문제라는 아이디어를 떠올림.

• 첫 번째 과정을 거쳐 점의 개수가 9개, 두 번째 과정을 거쳐 점의 개수가 25개라는 힌트를 통해 규칙을 찾고자 함.

• 정확한 규칙을 찾기 위해 3번째 과정까지 그림을 그려 확인한 후 나머지를 추론한 결과

• 1번 과정: 3X3 = 9

• 2번 과정: 5X5 = 25 (3 + 2^1)²

• 3번 과정: 9X9 = 81 (5 + 2^2)²

• 4번 과정: 17X17 = 289 (9 + 2^3)²

• 5번 과정: 33X33 = 1089 (17 + 2^4)²

• 한 변에 있는 점 개수에 2의 거듭제곱을 더한 값의 제곱이라는 규칙을 발견함.

• 초기 값 a(과정을 한 번도 돌리지 않은 상태에서 점의 개수가 4개라는 것을 고려)를 2로 설정.

• 거듭제곱 변수 b를 초기값 1로 설정.

• 과정이 반복될수록 거듭제곱 변수에 2를 곱한 후 그 값을 a 값에 더해주는 방식으로 알고리즘을 구상.

• 반복문이 완료된 후의 a 값을 제곱하여 결과값을 도출함.