☆ [백준/2903번/C++] 중앙 이동 알고리즘

• 문제

 

• 풀이

#include<iostream>

using namespace std;
int main()
{
	int n = 0, result = 0;
	int count = 2;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		count += count - 1;
	}

	result = count * count;

	cout << result;

	return 0;
}

 

• 메모
  초기 상태 (1)에서 점은 4개이고 그 다음엔 (2) 9개, (3) 25개.... (4) 1089개가 된다.
  여기서 규칙을 하나 찾을 수 있는데, 가로 점의 갯수만 따졌을 때
  
  가로가 2개면 점 4개
  가로가 3개면 점 9개
  
  여기까지 보면 점의 갯수는 가로의 점 갯수를 같은 값으로 제곱한 것과 같게 된다.
  
  그런데 이어지는 (3)의 경우 가로 점이 5개일 때 총점의 수는 25개가 되는데, 이는 점과 점 사이에 새로운 점(검정)이 한개씩 추가 되는 패턴이 있기 때문이다.
  
  즉, 최종적으로 가로의 점은 현재 점에서 하나를 뺀 값만큼 증가하게 된다는 걸 알 수 있다.
  
  이를 일반화된 식으로 나타내면
  
  현재 점 개수에서 다음 점이 추가된 값 = 2 * 점의 개수 - 1
  
  이 된다.
  
  초기 상태 (1)에서 최초의 점이 4개이므로, 가로 개수만 따지면 2개로 시작하기 때문에 count 값을 2로 초기화한 뒤
  n번만큼 반복하며 count += count-1을 해준 다음, 마지막으로 도출된 값을 동일 값으로 제곱해주면 최종 답을 얻을 수 있다.