백준 2903번 중앙 이동 알고리즘 (C++)

<일반 수학 1> 단계의 4번째 문제이다. 

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

 

이전 문제들은 여기서 볼 수 있다.

2025.03.19 - [코테] - 백준 2745번 진법 변환 (C++)

2025.03.20 - [코테] - 백준 11005번 진법 변환 2 (C++)

2025.03.20 - [코테] - 백준 2720번 세탁소 사장 동혁 (C++)

 

이번 문제는 외계 지형을 만드는 알고리즘을 만드는 것 이라고 말하고
규칙을 파악해서 식을 구하는 것이다.

 

규칙이 어렵지는 않아서 식을 금방 구할 수 있다. 

N 번 반복했을 때의 점의 개수는 한 줄의 점의 개수의 제곱이다. 

그렇다면 한 줄의 점의 개수만 구하면 되겠다고 생각했다. 

 

점이 늘어나는 규칙은 정사각형의 각 변의 중앙에 점을 추가하고, 정사각형의 중심에 점을 추가하는 것이다.

정사각형의 중심에도 점을 추가했기 때문에 모든 변이 점의 개수가 같다.

 

이제 입력으로 주어진 N번 반복했을 때의 한 변의 점의 개수를 일반화하면 된다.

점과 점 중앙에 새로운 점이 추가되므로 점 개수에 2를 곱하고, 마지막 점을 빼면 점의 갯수가 나온다.

 

내가 도출한 식이다.

N번째의 점 개수가 n, N-1 번째의 점 개수가 m 이라고 하면

이다. 

 

이제 이 내용을 알고리즘 화 해보자.

 

---

 

 

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;

	unsigned int D = 2;
	for (int i = 0; i < N; ++i) {
		D = 2 * D - 1;
	}

	cout << D * D;
}

위에서 설명한 내용을 알고리즘 화 한 결과이다.

 

초기 상태는 한 변에 점의 개수가 2인 정사각형 하나이기 때문에 D를 2로 선언한다.

입력한 N번 만큼 반복해서 더해야하기 때문에 D를 위에서 도출한 식으로 계속 갱신해준다.

 

N번 반복하고 나면 D는 한 변의 점의 개수가 저장되어 있을 것이고,

단순히 제곱해서 출력하면 된다.

 

---

이번 문제를 풀면서 내가 범했던 실수는..

 

제곱을 수행할 때 pow() 로 수행했다. 
pow 의 반환값은 double 이기 때문에 문제에서 요구한 형태로 출력되지 않는다.

 

 

---

마치며..

 

아무래도 수학 문제니까 알고리즘은 무궁무진할 것이라 생각이 든다. 

나는 한 변의 길이를 구해서 총 점의 개수를 구했지만, 

그냥 점의 개수 자체도 규칙이 있기 때문에 그 방법을 이용해도 될 것 같다.

나는 그것보다 일반화가 쉬운 방법을 택했다고 생각한다.

 

---

** 오류 지적은 환영입니다.^^ **