문제 개요
세 개의 정수 a, b, c가 주어졌다고 가정해 보겠습니다. 무한 수열의 첫 번째 항은 a이고, 공차(인접한 항 사이의 일정한 차이)는 c입니다. 이 문제의 목표는 b가 해당 수열 안에 존재하는지 판별하는 것입니다.
예를 들어 a = 1, b = 7, c = 3일 때 수열은 1, 4, 7, 10, ... 과 같이 전개됩니다. 여기에는 7이 포함되어 있으므로 출력 결과는 'Yes'가 됩니다.
해결 접근 방식
이 문제는 다음 두 가지 경우로 나누어 생각할 수 있습니다.
- c = 0인 경우: 공차가 0이면 수열의 모든 항은 a와 같습니다. 따라서 a와 b가 같으면 'Yes', 그렇지 않으면 'No'를 출력하면 됩니다.
- c ≠ 0인 경우: 어떤 음이 아닌 정수 k에 대해 b = a + k × c를 만족해야 합니다. 즉, (b − a) / c가 음이 아닌 정수여야 합니다. 코드에서는 (b − a) * c > 0 && (b − a) % c == 0 조건으로 검사할 수 있습니다. 첫 번째 조건은 b가 공차의 부호에 맞는 올바른 방향에 있는지를, 두 번째 조건은 차이가 공차로 나누어떨어지는지를 확인합니다.
C++ 구현 예시
#include <iostream>
using namespace std;
void isBInSequence(int a, int b, int c) {
// a == b 이거나, (b - a)가 c로 나누어떨어지고
// 방향 조건을 만족하면 'Yes' 출력
if (a == b || ((b - a) * c > 0 && (b - a) % c == 0))
cout << "Yes";
else
cout << "No";
}
int main() {
int a = 1, b = 7, c = 3;
cout << "The answer is: ";
isBInSequence(a, b, c);
return 0;
}
출력 결과
The answer is: Yes
동작 원리
a = 1, b = 7, c = 3인 경우를 단계별로 살펴보겠습니다.
- b − a = 6이고, 6 × 3 = 18 > 0이므로 방향 조건을 만족합니다.
- 6 % 3 = 0이므로 나누어떨어짐 조건도 만족합니다.
- 두 조건이 모두 참이므로 최종적으로 'Yes'가 출력됩니다.
반대로 a = 1, b = 8, c = 3이라면 8 − 1 = 7이 3으로 나누어떨어지지 않아 'No'가 출력됩니다. 또한 a = b인 경우에는 공차와 관계없이 항상 수열에 포함되므로 'Yes'가 됩니다.
이 알고리즘은 단순한 산술 연산만 사용하므로 시간 복잡도는 O(1)입니다. 입력 값의 크기와 관계없이 상수 시간 안에 결과를 얻을 수 있어 매우 효율적입니다.