[C++] 백준 17968번: Fire on Field

문제 링크

17968번: Fire on Field

문제 요약

수열 A의 $A[0]$와 $A[1]$은 1이다. i가 2 이상일 때, A[i]는 다음과 같이 구할 수 있다.
$k > 0$, $i - 2k \geq 0$인 모든 정수 k에 대해서
$A[i] - A[i - k] \neq A[i -k] - A[i - 2\times k]$를 성립하는 가장 작은 양의 정수가 A[i]가 된다.
N이 주어지면 $A[N]$을 출력해야 한다.

접근 방법

단순 구현, DP 문제였습니다. A[0], A[1]은 미리 값을 초기화시켜두고, A[2]부터는 1부터 값을 1씩 증가시켜가면서 모든 k에 대해서 조건을 성립하는지 확인해줍니다. 만약 성립하는 경우를 발견한다면 루프를 종료해주고 다음 A[i]값을 구해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	cin >> n;

	vector<int> a(n + 1);
	a[0] = a[1] = 1;

	for (int i = 2; i <= n; i++) {

		int num = 1;
		while (1) {
			bool flag = false;
			a[i] = num++;
			for (int j = 1; i - 2 * j >= 0; j++) {
				if (a[i] - a[i - j] == a[i - j] - a[i - 2 * j]) {
					flag = true;
					break;
				}
			}

			if (!flag)
				break;
		}
	}

	cout << a[n] << '\n';
	return 0;
}