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

문제 링크입니다. https://www.acmicpc.net/problem/2903

2903번: 중앙 이동 알고리즘

정사각형의 각 변의 중앙에 점을 추가한 뒤, 정사각형의 중심에 점을 추가합니다.
해당 과정을 N번 반복했을 때, N번까지 찍은 검은점의 갯수를 구하는 문제입니다.

초기상태에서는 점이 4개입니다. (한 변에 점 2개)
1번 반복했을 때는 점이 5개입니다. (한 변에 점 3(=2*2-1)개)
2번 반복했을 때는 점이 16개입니다. (한 변에 점 5(=3*2-1)개)
-> 2번 반복했을 때 찍은 점의 총 갯수는 25개입니다.

N번일 때, 검은 점과 흰 점의 갯수의 합은 (이전 변의 점의 갯수 * 2 - 1)^2개입니다.
이때, 흰 점의 개수를 N-1번일 때의 모든 점의 합입니다.

따라서, 식을 세워본다면, X*X - arr[N-1]이 됩니다.(X는 이전 변의 점의 갯수 * 2 - 1)

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int arr[16];
int N, x;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	arr[0] = 4;
	x = 2;
	for(int i = 1; i <= N; i++){
		x = x + x - 1;
		arr[i] = (x*x) - arr[i-1] + arr[i-1];
	}
	cout << arr[N];
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.