백준 17088번 등차수열 변환

문제

크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다.

수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가지가 있는데, 1을 더하거나 1을 빼는 것이다. 수열 B를 등차수열로 변환하기 위해 필요한 연산 횟수의 최솟값을 구해보자.

입력

첫째 줄에 수열 B의 크기 N(1 ≤ N ≤ 105)이 주어진다. 둘째 줄에는 B1, B2, ..., BN(1 ≤ Bi ≤ 109)이 주어진다.

출력

수열 B를 등차수열로 변화시키기 위한 연산 횟수의 최솟값을 출력한다. 등차수열로 변환시킬 수 없다면 -1을 출력한다.

 

착각한것이 연산을 한 수에 한번이 최대 적용이였던 것이였다.....

아무튼 사이즈가 1이면 그냥 0출력하면 되고, 그 이후는 첫번째 수와 두번째 수의 차이가 이후 모든 두수의 차이와 같아야 하므로, 첫번째 수와 두번째 수의 차이를 나타내는 케이스 9가지로 등차가 모두 결정된다.

따라서 9개의 케이스로 등차를 구하고 세번째 수부터 탐색하면서 +1,-1 연산만으로 만들 수 있는지 확인하고 없으면 탈출한다.

결국 무사 통과시에 그 연산 수를 출력하는 것으로 마무리.

 

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int MAX = 100000;
int N;
vector<int> vec;
vector<int> res;
int ans = 987654321;



int main(void)
{
	cin >> N;

	if (N == 1)
	{
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i < N; i++)
	{
		int b;
		cin >> b;
		vec.push_back(b);
	}
	for (int d1 = -1; d1 <= 1; d1++)
	{
		for (int d2 = -1; d2 <= 1; d2++)
		{
			int cnt = 0;
			if (d1 != 0)
			{
				cnt++;
			}
			if (d2 != 0)
			{
				cnt++;
			}
			int diff = (vec[1] + d2) - (vec[0] + d1);
			bool flag = true;

			int cand = vec[1] + d2;
			for (int i = 2; i < N; i++)
			{
				cand += diff;
				if (vec[i] == cand)
				{
					continue;
				}
				else if (vec[i] + 1 == cand)
				{
					cnt++;
				}
				else if (vec[i] - 1 == cand)
				{
					cnt++;
				}
				else
				{
					flag = false;
					break;
				}
			}

			if (flag)
			{
				if (ans > cnt)
				{
					ans = cnt;
				}
			}
		}
	}
	
	if (ans == 987654321)
	{
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;
}