[BOJ] 17088: 등차수열 변환

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

17088번: 등차수열 변환

 

 

간단하게 생각해서 모든 원소에 -1 연산을 수행하는 경우, 아무 연산도 적용하지 않는 경우, +1 연산을 수행하는 경우로 나눌 수 있다.

 

하지만 입력의 최댓값이 수열 B의 크기가 N(1 ≤ N ≤ 10^5), 원소의 크기가(1 ≤ Bi ≤ 10^9)로 매우 크기 때문에 시간 복잡도가 O(3^N)인 이 알고리즘으론 최악의 경우 무려 3^(10^5)...

 

그렇다면 무식하게 풀더라도 다른 방법을 선택해야 한다.

각각의 원소에 연산을 한 번만 적용 가능하기 때문에 가능한 초항의 수는 A[0] - 1, A[0], A[0] +1의 3가지밖에 없으니, 공차만 알 수 있다면 등차수열을 만들 수 있는지 알 수 있을 것이다.

 

M = 가능한 원소의 값의 수일 때 O(NM)으로 가능한 모든 공차를 시도해 보는 것은 어떨까?

하지만 원소의 크기가(1 ≤ Bi ≤ 10^9)이기 때문에 공차는 [(-2) * 10^9, 2 * 10^9]의 엄청난 범위를 가진다.

4*10^5*10^9이니, 시간 제한이 1초인 이 문제에서는 다른 방법을 찾아야 한다.

 

이 문제를 풀기 위해선 등차수열의 성질과 문제의 조건을 이용하면 된다.

 

우리는 앞서 가능한 초항의 수가 A[0] - 1, A[0], A[0] +1의 3가지라고 말했다.

그리고, 가능한 두번째 항의 수 또한 A[1] - 1, A[1], A[1] +1의 3가지 뿐이다.

 

공차 d는 d = a[n] - a[n-1]을 만족해야 등차수열이기 때문에, 초항과 두번째 항을 안다면 우리는 공비를 가정할 수 있다.

 

이제 이 초항, 두번째 항과 공비를 통해 등차수열을 만들 수 있는지만 판단하면 된다.

 

const int IMPOSSIBLE = 10e8;

 

먼저, 통상적으론 나올 수 없는 불가능한 값을 정해준다.

경우의 수에 +1을 해주는 연산이 있기 때문에, 산술 오버플로우에 주의하자.

 

int ret = 0;
if (N > 1) {
  ret = std::min(std::min(start(B[0] - 1) + 1, start(B[0])), start(B[0] + 1) + 1);
}

 

초항과 두번째 항을 정할 수 없는 예외가 존재한다.

수열의 크기가 1일 때는 그 자체로 등차수열이라고 할 수 있기 때문에 추가적인 연산이 필요 없다. 따라서 이 때는 0을 출력해준다.

 

초항에 1을 빼거나 더한 경우는 경우의 수에 +1을 해주고, 연산을 적용하지 않은 경우는 그대로 놔둔다.

 

int start(const int a1) {
	int diff = B[1] - a1;
	int ret = std::min(solve(diff, B[1]), solve(diff + 1, B[1] + 1) + 1);
	ret = std::min(ret, solve(diff - 1, B[1] - 1) + 1);
	return ret;
}

 

두 번째 항을 정한다.

역시 초항과 비슷한 방법이다.

 

int solve(int d, int current, int index = 1) {
	if (index + 1 == N) return 0;
	int next = B[index + 1];
	int diff = next - current - d;

	if (-1 <= diff && diff <= 1) {
		return solve(d, next - diff, index + 1) + ((diff == 0) ? 0 : 1);
	}
	else return IMPOSSIBLE;
}

 

반복문을 사용해도 되지만, 나는 리커전을 좋아하기 때문에 리커전으로 구현했다.

현재 수와 다음 수가 있을 때, 다음 수와 현재 수의 차는 [d - 1, d + 1] 범위 안의 값이 되어야 1을 더하거나 빼는 것으로 등차수열을 만들 수 있다. 때문에 diff는 [-1, 1] 범위에서 존재해야 한다.

 

전체 코드

 

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

int N;
std::vector<int> B;

const int IMPOSSIBLE = 10e8;

int solve(int d, int current, int index = 1) {
	if (index + 1 == N) return 0;
	int next = B[index + 1];
	int diff = next - current - d;

	if (-1 <= diff && diff <= 1) {
		return solve(d, next - diff, index + 1) + ((diff == 0) ? 0 : 1);
	}
	else return IMPOSSIBLE;
}

int start(const int a1) {
	int diff = B[1] - a1;
	int ret = std::min(solve(diff, B[1]), solve(diff + 1, B[1] + 1) + 1);
	ret = std::min(ret, solve(diff - 1, B[1] - 1) + 1);
	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
	std::cin >> N;
	B.resize(N);
	for (int i = 0; i < N; ++i) {
		std::cin >> B[i];
	}

	int ret = 0;
	if (N > 1) {
		ret = std::min(std::min(start(B[0] - 1) + 1, start(B[0])), start(B[0] + 1) + 1);
	}
	std::cout << ((ret == IMPOSSIBLE) ? -1 : ret);

	return 0;
}