알고리즘

  1. 첫번째와 두번째 원소 사이의 공차를 구함
  2. 두번째 원소부터 마지막원소까지의 공차를 만족하는 경우만으로 dfs를 진행함
    1. 마지막원소까지 공차를 만족하는 모든 경우의 수를 구하고, 그 중 최소 연산으로 만족하는 경우의 수를 반환함.
  3. 위 과정을 첫번째 원소와 두번째 원소 사이의 공차의 경우의수만큼 진행하고, 그 중에서 최소 연산의 수를 구한다.
    1. 각 원소별로, (-1, 0, 1) 세 개의 연산을 할 수 있으므로 공차의 경우의 수는 9개.

삽질

  1. 다이나믹을 적용할 수 있을거라 생각했다.
    • 현재 depth의 원소가 depth와 이전 depth에서 어떤 연산을 적용받은 결과인지로, 현재 depth의 상태가 결정된다고 생각하였기에.
    • 하지만, 현재 depth의 상태는 depth와 현재 원소의 값으로 결정되었다.
    • 하지만 원소의 값은 최대 10억이므로 다이나믹에 사용하기엔 무리가 있었다
  2. 현재 depth에서, 현재 depth와 다음 depth에 모두 연산을 적용하였다.
    • 양쪽을 모두 연산 시켜줘야 모든 경우를 탐색하는 것이라 생각했기에 그리하였는데, 당연히 정답코드에 비해 매 깊이마다 3배의 계산을 하게 되므로 시간초과가 났다
    • 하지만 이는 매우 많은 중복계산을 불러일으키고, 매 깊이에서 다음 depth의 연산만 해줘도 충분히 모든 경우를 탐색할 수 있었다.

코드

#include <iostream>
#define INF 2000000000
using namespace std;
 
int n, ans = INF, os[9][2] = { {0,0}, {0, 1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {-1, -1}, {-1, 0}, {-1, 1} };
int diff, nums[100010];
 
int min(int a, int b) {
	return a < b ? a : b;
}
int abs(int a) {
	return a < 0 ? -a : a;
}
 
int dfs(int d, int prev) {
	if (d == n - 1)
		return 0;
 
	int res = INF;
	for (int j = -1; j <= 1; j++) {
		nums[d + 1] += j;
 
		if ((nums[d + 1] - nums[d]) == diff)
			res = min(res, dfs(d + 1, j) + abs(j));
 
		nums[d + 1] -= j;
	}
	return res;
}
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> nums[i];
	if (n <= 2) {
		cout << 0;
		return 0;
	}
 
	for (int i = 0; i < 9; i++) {
		nums[0] += os[i][0]; nums[1] += os[i][1];
		diff = nums[1] - nums[0];
 
		ans = min(ans, dfs(1, nums[1]) + abs(os[i][0]) + abs(os[i][1]));
		nums[0] -= os[i][0]; nums[1] -= os[i][1];
	}
 
	if (ans >= INF - 200000)
		cout << -1;
	else
		cout << ans;
}