[백준] 2903번 : 중앙 이동 알고리즘 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2903번: 중앙 이동 알고리즘

 

1. 문제 설명

2. 풀이과정

해당 문제는 과정을 반복할 때마다 생기는 점의 개수를 구하는 문제이다.

생기는 점의 개수에는 규칙이 존재하는데, 이는 해당 과정을 반복할 때마다 한 변에 추가로 생기는 점의 개수는 이전  한 변의 중앙 지점의 개수만큼 점이 추가로 생긴다.

처음에는 한 변에 점이 2개이다. 이후 과정을 1회 수행하면 변의 가운데에 점이 하나 생겨 한 변에 점이 3개가 된다.

이후 또 과정을 1회 수행하면 한 변이 2개의 구역으로 나누어져 있는 상태에서 각 변의 가운데에 점이 생겨 2개의 점이 추가되어 총 5개의 점이 생긴다.

해당 규칙을 보면 2개 → 2개 + 1개 → 2개 + 1개 + 2개 → 2개 + 1개 + 2개 + 4개 ... 로 한 변의 점이 늘어나게 된다.

이를 식으로 구현해 보면 2 → 2+2**0 → 2+2**0+2**1 → 2+2**0+2**1+2**2 ... 의 규칙을 가지게 되어, 처음 변의 개수 2에 과정을 반복할 때마다 2의 배수로 점이 추가로 생기는 것을 볼 수 있다.

총 과정 이후 한 변의 점 개수 : 2 + ∑2**i (i = 0~n -1)

그리고 변의 개수를 보면, 변의 개수는 한 변에서 점의 개수와 동일한 것을 볼 수 있다.

하여 총 점의 개수는 한 변의 점의 개수를 제곱하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 과정을 반복할 횟수를 입력받는다. N = int(sys.stdin.readline())
3. 한 변에 점의 개수를 저장할 변수를 생성하고 초기 점의 개수인 2개를 저장한다. dot = 2
4. 과정을 반복하며 for i in range(N)
5. 한 변의 점의 개수에 해당 과정을 반복할 때마다 추가로 생기는 점의 개수를 더해준다. dot += 2 ** i
6. 총 점의 개수는 한 변의 점의 개수가 총 해당 점의 개수만큼 변이 존재하므로 점의 개수를 곱해주면 된다. 하여 결과를 출력한다. print(dot * dot)

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
dot = 2
for i in range(N):
    dot += 2 ** i
    
print(dot * dot)