개요

등차수열을 수학 시간에 쉽게 배웠는데 알고리즘 문제들을 보면 등차수열의 개념을 이용하되 어렵게 만든 문제들이 꽤 있는데 이를 공략해보자

수열이란?
일정한 규칙에 따라 수를 나열한 집합을 의미한다. 각각의 수를 항이라고 부른다

등차수열 개념

등차수열은 각 항과 그 다음의 항의 차이가 일정한 수열을 의미한다. 인접한 두 항의 차이를 공차라고 나타냄

1, 4, 7, 10, ...

수열의 시작 항(초항)을 $a$라고 하고 공차를 $d$라고 해보자

그러면 다음을 구할 수 있다

• 등차수열의 $n$번째 항 : $a_n = a + (n - 1)d$
• 등차수열의 합
  • 등차수열의 $n$번째 항까지 합을 구하면
  • $S_n = n(a_1 + a_n) / 2$

문제

백준 14913번

문제

풀이

공식만 사용하면 쉬운 문제이다. 사실 $a_n = a + (n - 1)d$를 이용해 n을 1부터 시작해서 루프를 돌아가며 k가 등차 수열에 포함되는지 확인해도 되는데 이렇게 되면 아무래도 루프를 돌아야 한다

O(1)의 시간으로 구하는 방법이 있을까??

위의 식을 생각해보면 n이 등차수열의 n번째 항이고 우리가 문제에서 구하는 건 n이다. 그러면 위의 식을 n에 대해 정리해보면 되지 않을까??

문제에서 k가 몇 번째 항인지 궁금하니 $a_n$에 k를 넣자

1. $k - a = (n - 1)d$
2. $(k - a)/d = n - 1$
3. $(k - a)/d + 1 = n$

와 같이 정리할 수 있다. 그러면 우리는 a, d, k를 아니까 대입할 수 있다

이제 k가 등차수열의 항인지 확인하려면 n이 자연수라는 성질을 활용한다

즉 $(k - a)/d$가 정수여야 하니까 $(k - a)$가 d의 배수여야 한다. 그리고 $(k - a)/d$가 0보다 큰 지 확인하고 n을 출력한다

코드

#include <bits/stdc++.h>

using namespace std;

int a, d, k;

void Input() 
{
	cin >> a >> d >> k;
}

void Solve()
{
	int diff = k - a;

	if ((diff % d == 0) && ((diff / d) >= 0))
	{
		cout << (diff / d + 1);
	}
	else
	{
		cout << "X";
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	Solve();

	return 0;
}

백준 17088번 : 등차수열 변환

문제

풀이

이 문제는 등차수열을 이용한 경우의 수를 구하는 문제이다

문제를 이해하자면 수열의 각 항이 있을 때 각 항에 -1, 1을 더해 수정하거나 그대로 둬서 결국 수열이 등차수열로 만들 수 있는 최소 수정 횟수를 구하는 문제이다

4
24 21 14 10

을 입력 예시로 생각해보자

24에 1을 더하고, 21에 -1을 더하고, 14에 1을 더하면 공차가 5인 등차수열이 완성되어 최소 수정 횟수가 3이 나오는 예시이다

등차수열의 경우 첫 번째 항과 두 번째 항으로 공차가 결정나고 세 번째 항부터 등차수열에 포함되는 지 확인하면 된다

그래서 생각한 방법은 먼저 등차를 고정시키고 수열이 등차수열인지 확인한다

등차를 고정시키는 방법은 첫 번째 항과 두 번째 항의 수정 여부에 따라 달렸다

가능한 등차의 경우 9가지 경우의 수가 있는데 첫 번째 항에 [-1, 0, 1]을 더하고 두 번째 항에 [-1, 0, 1]을 더하는 방법을 곱한 9가지이다

그렇게 등차를 고정시킨 뒤 3번째 항부터 공식을 이용해 수열에 포함되는 지 확인하면서 최소 연산 횟수를 수정해나가면 된다

확인할 때는 절댓값이 1 이하인지 확인해주고 수정 횟수를 늘려야 한다

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int B[100004];
int answer = INT_MAX;

void Input() 
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> B[i];
	}
}

void Solve()
{
	for (int i = -1; i <= 1; i++)
	{
		for (int j = -1; j <= 1; j++)
		{
			int b_0 = B[0] + i;
			int b_1 = B[1] + j;
			int d = b_1 - b_0;

			int cnt = abs(i) + abs(j);
			bool check = true;

			for (int k = 2; k < N; k++)
			{
				int b_k = b_0 + k * d;

				if (abs(B[k] - b_k) > 1)
				{
					check = false;
					break;
				}
				else if (B[k] != b_k)
				{
					cnt++;
				}
			}

			if (check) answer = min(answer, cnt);
		}
	}

	if (answer == INT_MAX)
	{
		cout << -1;
	}
	else
	{
		cout << answer;
	}
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	Solve();

	return 0;
}