백준 17088번 등차수열 변환

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

17088번: 등차수열 변환

 

 

 

 

 

 

<접근방법>

모든 수에 대하여 -1, 0, +1 연산을 적용시켜서 경우의 수를 계산하면 N의 크기가 10^5이기 때문에

시간 초과가 납니다.

 

인접한 숫자들은 서로 연관되어 있습니다.

뒤에 있는 숫자가 앞의 숫자에 맞춰서 등차수열의 관계를 유지할 필요가 있습니다.

이렇게 생각한다면 모든 경우의 수들에 대해서 생각할 필요가 없어집니다.

앞의 숫자의 스탠스만 정해주면 되니까요.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

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

int n;
int a[100001], b[100001];

void reset() {
	for (int i = 0; i < n; i++) {
		a[i] = b[i];
	}
}

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

	if (n == 1) {
		cout << 0 << '\n';
		exit(0);
	}
	
	int res = 987654321;
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			reset();
			int tres = 0;
			if (i != 0) tres++;
			if (j != 0) tres++;

			a[0] += i;
			a[1] += j;
			int diff = a[0] - a[1];
			bool suc = true;
			for (int k = 2; k < n; k++) {
				int tdiff = a[k-1] - a[k];
				
				bool flag = false;
				for (int l = -1; l <= 1; l++) {
					if (tdiff + l == diff) {
						flag = true;
						a[k] -= l;
						if (l != 0) {
							tres++;
						}
						break;
					}
				}
				if (!flag) {
					suc = false;
					break;
				}
			}
            
			if (suc) {
				res = min(res, tres);
			}
		}
	}

	if (res == 987654321) cout << -1 << '\n';
	else cout << res << '\n';

	return 0;
}