[백준:2903/Python] 중앙 이동 알고리즘

문제 요약 

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

2. 정사각형의 중심에 점을 하나 추가한다. 

 

출처 - 백준

 

문제 풀이

오늘도, 선 정답 후 풀이를 하려 한다. 

내가 푼 풀이는 아래와 같다. 

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

 

생각보다 단순한 코드였다. 

 

먼저, 점의 개수가 늘어나는 규칙을 찾아본다면, 

초기 -> 점 4개 

N=1 -> 점 9개 

N=2 -> 점 25개 

N=3 -> 점 81개 

이다. 

 

이를 풀어서 작성한다면, 

4 =2**2 

9 = 3**2

25 = 5**2

81= 9**2 

이렇게 된다. 

그럼 여기서 알 수 있는 것은 

 

사진에서 처럼 보이는 한 변의 길이만 구한 뒤, 정사각형의 넓이 구하는 형식(가로 * 세로)으로 풀면 점의 개수를 구할 수 있다는 것이다. 

여기서 변의 길이라고 하니, 헷갈릴 수 있겠지만 사각형의 가로 또는 세로에 배치된 점의 개수라고 생각하면 된다. 

즉, 위의 사진처럼 빨간색 으로 각각 동그라미 쳐둔 것이 변의 길이라고 할 수 있다. 

 

그렇다면 변의 길이는 어떻게 증가하고 있을까?

변의 길이를 각각 따오면, 2,3,5,7 이다. 

이를 확인해보면

처음 변의 길이 = 2 
2 + 1 = 3 
3 + 2 = 5 
5 + 4 = 9
9 + 8 = 17 

로 증가하는 규칙을 갖고 있다. 

여기서 1,2,4,8 은 생각해 본다면 

(이전 변의 길이 - 1)이라는 것을 알 수 있다. 

처음 변의 길이 = 2 
2 + 1(->2-1) = 3 
3 + 2(->3-1)= 5 
5 + 4(->5-1) = 9
9 + 8(->9-1) = 17 

 

그럼 이제 이 부분만 잘 보면 된다. 

마지막으로 그 증가된 변의 길이에, 더해지는 숫자들은 

첫 번째 1을 제외하고 2,4,8...로 2의 N승인 것을 확인할 수 있다. 

즉, 2**1, 2**2, 2**3,..으로 1,2,3이 N번씩 과정을 거치고 있다는 것이다. 

 

그렇다면 이제 아까 정답으로 공개한 내 풀이를 보면 이해할 수 있게 된다.

1은 제외됐으니, 2의 N승 앞에 +1을 해준 것이며, 이를 통해서 구해진 변의 길이에 변의 길이를 곱하기 위해서 제곱근 2를 해줌으로써 

점의 개수를 구할 수 있게 된다. 

 

 

끝!