백준 17088번 등차수열 변환

문제 링크입니다: https://www.acmicpc.net/problem/17088

17088번: 등차수열 변환

N의 크기가 최대 100,000이기 때문에 모든 경우의 수를 고려하는 코드를 작성할 경우 TLE가 발생할 것이 자명합니다.

따라서, 등차수열의 규칙을 생각해봐야 합니다.

수학에서, 등차수열은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻합니다.

따라서, 등차수열이기 위해서는 (두 번째 숫자 - 첫 번째 숫자)의 차가 (세 번째 숫자 - 두 번째 숫자), (네 번째 숫자 - 세 번째 숫자), ..., (N 번째 숫자 - (N - 1) 번째 숫자)와 동일해야합니다.

즉, 두 번째 숫자와 첫 번째 숫자를 각각 독립적으로 [-1, 0, 1]한 결과를 토대로 등차수열을 유지할 수 있는지 연산해나가면 시간복잡도가 O(9 * N)이기 때문에 TLE 발생을 걱정하지 않아도 됩니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	if (N == 1)
	{
	cout << 0 << "\n";
	return 0;
	}
	vector<int> v(N);
	for (int i = 0; i < N; i++)
	{
	cin >> v[i];
	}
	int result = -1;
	for (int add = -1; add <= 1; add++)
	{
	for (int add2 = -1; add2 <= 1; add2++)
	{
	int tempCnt = 0;
	tempCnt = add ? tempCnt + 1 : tempCnt;
	tempCnt = add2 ? tempCnt + 1 : tempCnt;
	int diff = (v[1] + add2) - (v[0] + add);
	bool isPossible = true;
	int next = v[1] + add2;
	for (int i = 2; i < N; i++)
	{
	next += diff;
	if (v[i] == next)
	{
	continue;
	}
	if (v[i] + 1 == next || v[i] - 1 == next)
	{
	tempCnt++;
	continue;
	}
	isPossible = false;
	break;
	}
	if (isPossible)
	{
	if (result == -1)
	{
	result = tempCnt;
	continue;
	}
	result = min(result, tempCnt);
	}
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~