C++로 특정 숫자가 주어진 첫 항과 공차를 가진 등차수열(AP)에 속하는지 확인하는 방법

등차수열(AP)이란?

등차수열(Arithmetic Progression, AP)은 연속된 두 항의 차이가 일정한 수열입니다. 첫 항 a와 공차(차이) d가 주어지면 수열의 모든 항은 다음과 같은 일반항으로 표현할 수 있습니다.

x = a + n × d (n은 0 이상의 정수)

예를 들어 첫 항 a = 1, 공차 d = 3이라면 수열은 1, 4, 7, 10, ... 형태가 됩니다. 이때 x = 7이 이 수열에 포함되는지 확인하면, 7 = 1 + 2 × 3이므로 답은 '예'입니다.

문제 해결 접근 방법

주어진 숫자 x가 해당 등차수열의 항인지 확인하기 위해 다음 단계를 따릅니다.

• 공차 d가 0인 경우: 수열의 모든 항이 첫 항 a와 같으므로, x가 a와 같으면 true, 그렇지 않으면 false를 반환합니다.
• 공차 d가 0이 아닌 경우: x = a + n × d (n은 음수가 아닌 정수) 형태로 표현 가능한지 확인합니다. 즉, (x − a)가 d로 나누어떨어지고, 그 몫 (x − a) / d가 0 이상이면 true입니다.

C++ 예제 코드

#include <iostream>
using namespace std;

bool isInAP(int a, int d, int x) {
    if (d == 0)
        return (x == a);
    return ((x - a) % d == 0 && (x - a) / d >= 0);
}

int main() {
    int a = 1, x = 7, d = 3;
    if (isInAP(a, d, x))
        cout << "The value " << x << " is present in the AP";
    else
        cout << "The value " << x << " is not present in the AP";
}

코드 설명

isInAP 함수는 세 개의 매개변수(첫 항 a, 공차 d, 확인할 값 x)를 받습니다. 먼저 공차가 0인지 검사하고, 0이 아니라면 두 조건을 동시에 확인합니다.

• (x - a) % d == 0: x − a가 공차로 나누어떨어지는지 확인합니다.
• (x - a) / d >= 0: 해당 항이 수열에서 첫 항 이후에 위치하는지, 즉 n이 음수가 아닌 정수인지 확인합니다.

두 조건을 모두 만족해야만 x가 유효한 등차수열의 항으로 인정됩니다.

실행 결과

The value 7 is present in the AP

a = 1, d = 3으로 생성된 수열 {1, 4, 7, 10, ...}에는 7이 포함되므로 위와 같은 결과가 출력됩니다. 이 방법은 시간 복잡도 O(1)로 매우 효율적이며, 어떤 크기의 등차수열에 대해서도 빠르게 판별할 수 있습니다.