[PS] 백준 17088번 등차수열 변환

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

등차수열 변환 문제이다. n개의 숫자가 순서대로 주어지고 각 숫자에 최대 한 번의 연산을 수행할 수 있다. 연산은 1을 더하거나 뺀다. 주어진 수열을 등차수열로 변환하는 최소 연산횟수를 구하면 된다. 불가능한 경우 -1을 출력한다.

모든 경우의 수를 구한다면, 그대로 두는 경우와 1을 더거나 1을 빼는 경우 3가지가 있으므로 3 ^ n 이 가능 할 것이다. 1 <= n <= 100000 이므로 당연히 시간초과이다.

그러나 등차수열이라는 제한을 적용하여 경우의 수를 줄일 수 있다. 초항과 공차가 등차수열의 일반항을 정의하므로 초항과 공차를 변수로 두면 된다. 그래서 가능한 초항의 값 3가지 가능한 마지막항 값 3가지 동시에 일어나므로 3 * 3 = 9 가지의 등차수열 후보를 고려하면 된다.

공차를 구하고, 초항과 공차를 이용하여 등차수열의 i번째 항을 구한다. 구한 값과 입력 숫자를 비교해서 그대로 혹은 연산을 적용하여 같아질 수 있다면 다음 항을 비교한다. n - 2번 (초항과 마지막항 제외) 비교하면 조건을 만족하면서 등차수열로 변환할 수 있는지와 연산횟수를 구할 수 있다.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n, ans= 100001;
int nums[100000];

int checkSeries(int candidateFisrt, int commonDiff) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int tobe = candidateFisrt + commonDiff * i;
		int asis = nums[i];

		int gap = abs(tobe - asis);
		if (gap > 1) {
			cnt = -1;
			break;
		}

		cnt += gap;
	}

	return cnt;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}

	if (n == 1) {
		cout << 0 << '\n';
		return 0;
	}

	for (int first = -1; first <= 1; first++) {
		for (int last = -1; last <= 1; last++) {
			int candidateFisrt = nums[0] + first;
			int candidateLast = nums[n - 1] + last;

			int diff = candidateLast - candidateFisrt;
			if (diff % (n - 1) != 0) {
				continue;
			}

			int commonDiff = diff / (n - 1);

			int cnt = checkSeries(candidateFisrt, commonDiff);
			if (cnt >= 0) {
				ans = min(ans, cnt);
			}
		}
	}

	if (ans == 100001) {
		cout << -1 << '\n';
		return 0;
	}
	cout << ans << '\n';
	return 0;
}