[17968/c++] Fire on Field

<문제>

 간단하게 요약하면 등차수열을 만들지 않는 최소의 양의 정수를 구하는 것이었다. 아오 근데 맨날 알고리즘 문제는 영어라서 나는 한참을 읽고...또 읽는다. 방학되면 영어 공부 제대로 해야지;;;

 

<풀이>

 일단 값에 1을 대입하고 검사를 한다. 조건은 k > 0 , i − 2k ≥0,  A[i] − A[i − k] ≠ A[i − k] − A[i − 2k].

만약에 조건을 위배하면 즉 등차수열이 완성되면 1을 더해준다. 여기서 고려해야할 점은 1을 더한 후에 또 등차수열을 만들지는 않는지 검사를 해줘야한다. 이게 숫자가 작으면 상관없는데 8이상이 되면 문제가 생기기 때문임 그래서 어떻게 검사를 또 시킬까 하다가 걍 재귀함수 사용함 덕분에 4ms나 걸림

 

 

#include <iostream>
using namespace std;

void check(int *a, int i, int n, int num) {
	for (int k = 1; i - 2 * k >= 0; k++) {
		if (a[i] - a[i - k] == a[i - k] - a[i - 2 * k]) {
			n++;
			a[i] = n;
			check(a, i, n, num);
		}
	}
}
int main() {
	int a[1001];
	a[0] = 1;
	a[1] = 1;

	int num;
	cin >> num;
	for (int i = 2; i <= num; i++) {
		int n = 1;
		a[i] = n;

		check(a, i, n, num);
	}
	cout << a[num] << endl;
}