[구현/수학] 백준 2903 중앙 이동 알고리즘 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2903번: 중앙 이동 알고리즘

 

 

 

2. 문제 풀이

 규칙에 따라 점의 개수를 구해야 합니다.

 

초기상태 4개 / 1회 9개 / 2회 25개

1. 정사각형의 각 변의 중앙에 점을 하나 추가
2. 정사각형의 중심에 점을 하나 추가

 

 문제에 흰점과 검은점이 섞여 있어서 오히려 더 어렵게 보이기도 합니다. 색깔 구분없이 보면, 그저 빽빽하게 점이 채워진 정사각형이 보입니다. 즉, 변의 길이만 알면 점의 개수를 구할 수 있습니다.

 

 처음에는 변의 길이가 2였고, 그 다음은 3, 5로 증가합니다. 다음은 점 5개 사이에 점이 1개씩 추가되므로, 변의 길이는 9가 됩니다.

 즉 (이전 변의 길이 - 1) 만큼씩 변의 길이가 늘어납니다.

 

초기) 2
1회) 2 + 1 = 3
2회) 3 + 2 = 5
3회) 5 + 4 = 9
4회) 9 + 8 = 17
5회) 17 + 16 = 33

 늘어나는 길이를 나열해보면, 더 직관적인 규칙을 찾을 수 있습니다. 2의 배수만큼 늘어나며, n회 차의 변의 길이는 (1 + 2**n)입니다.

 

 

3. 코드

# 입력
n = int(input())

# 점의 개수 계산
side = (1 + 2**n)
print(side**2)