[백준] 17088 등차수열 변환

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

17088번: 등차수열 변환

#include <iostream>
#include <vector>
using namespace std;

long long arr[100010];
vector <long long> choice;
int n;
int answer = 987654321;
const int cal[3] = {0, -1, 1};

bool checker(long long no, long long diff, int cnt) {

	if(diff == no - choice[cnt-1])
		return true;
	return false;
}


void dfs(int idx, int cnt, int add, int target) {

	if(cnt == target) {
		if(answer > add)
			answer = add;
		return;
	}

	if(cnt < 2){
		for(int j=0; j<3; j++) {
			choice.push_back(arr[idx]+cal[j]);

			if(j != 0)
				dfs(idx+1, cnt+1, add+1, target);
			else
				dfs(idx+1, cnt+1, add, target);
			choice.pop_back();
		}
	}
	else {
		// check diff
		long long diff = choice[1] - choice[0];
		long long last_v = choice[cnt-1];

		for(int i=0; i<3; i++) {
			long long next_v = arr[idx] + cal[i];
			if(diff == next_v - last_v) {
				choice.push_back(next_v);
				if(i != 0)
					dfs(idx+1, cnt+1, add+1, target);
				else
					dfs(idx+1, cnt+1, add, target);
				choice.pop_back();
			}
		}

	}


}



int main() {
	scanf("%d", &n);

	for(int i=0; i<n; i++) {
		scanf("%lld", &arr[i]);
	}

	int idx = 0;
	for(int i=0; i<3; i++) {
		long long next_v = arr[0] + cal[i];
		choice.push_back(next_v);
		if(cal[i] != 0)
			dfs(1, 1, 1, n);
		else
			dfs(1, 1, 0, n);
		choice.pop_back();
	}

	if(answer == 987654321) {
		printf("-1\n");
		return 0;
	}

	printf("%d\n", answer);
}

수열의 길이는 정해져있고, 순서마다 들어가야 하는 원소가 같으므로 각 depth 에 맞는 원소들을 넣어주면 된다.

depth 0 : 첫번째 원소, 첫번째 원소-1, 첫번째 원소+1

depth 1 : 두번째 원소, 두번째 원소-1, 두번째 원소+1

 

하지만, 이런식으로 모든 케이스를 생성한 후 검증하게 되면, 시간초과가 난다.

그렇기 때문에 각 원소들을 집어넣기 전에 넣어도 되는지 검증하는 과정을 거친다.