C++ 프로그램 – 무작위로 선택한 세 숫자가 등차수열(AP)일 확률 구하기

양의 정수로 이루어진 배열이 주어졌을 때, 이 배열에서 무작위로 선택한 세 개의 숫자가 등차수열(Arithmetic Progression, AP)을 이룰 확률을 구하는 것이 목표입니다.

여기서 등차수열이란 연속된 두 항의 차이(공차)가 일정한 수열을 의미합니다. 예를 들어 {2, 4, 6}처럼 세 숫자 a, b, c가 2b = a + c 관계를 만족하면 등차수열이라고 할 수 있습니다.

예시

입력-: arr[] = { 2,3,4,7,1,2,3 }
출력-: 무작위로 선택한 세 숫자가 등차수열일 확률: 0.107692

입력-: arr[] = { 1, 2, 3, 4, 5 }
출력-: 무작위로 선택한 세 숫자가 등차수열일 확률: 0.151515

접근 방식

이 문제는 배열의 실제 값과는 상관없이 배열의 크기(n)만으로 확률을 계산할 수 있다는 점이 흥미롭습니다. 아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

양의 정수로 이루어진 배열을 입력받습니다.
배열의 크기(n)를 계산합니다.
다음 수학적 공식을 적용하여 무작위로 선택한 세 숫자가 등차수열일 확률을 구합니다.

확률 = 3n / (4n² − 1)
계산된 결과를 출력합니다.

이 공식은 전체 경우의 수 중에서 등차수열을 이루는 조합의 비율을 나타낸 것으로, 배열의 원소 개수가 늘어날수록 확률이 감소하는 경향을 보입니다.

알고리즘

Start
Step 1-> 무작위로 선택한 세 숫자가 등차수열일 확률을 계산하는 함수 정의
    double probab(int n)
        return (3.0 * n) / (4.0 * (n * n) - 1)
Step 2-> main() 함수에서
    배열 선언: int arr[] = { 2,3,4,7,1,2,3 }
    배열 크기 계산: int size = sizeof(arr)/sizeof(arr[0])
    probab(size) 함수를 호출하여 확률 계산 후 출력
Stop

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 무작위로 선택한 세 숫자가 등차수열일 확률 계산
double probab(int n) {
    return (3.0 * n) / (4.0 * (n * n) - 1);
}

int main() {
    int arr[] = { 2,3,4,7,1,2,3 };
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << "무작위로 선택한 세 숫자가 등차수열일 확률: " << probab(size);
    return 0;
}

출력 결과

무작위로 선택한 세 숫자가 등차수열일 확률: 0.107692

코드 설명

위 코드에서 probab() 함수는 배열의 크기 n을 매개변수로 받아 공식 3n / (4n² − 1)을 그대로 반환합니다. 정수 나눗셈으로 인한 오차를 방지하기 위해 3.0, 4.0처럼 실수형 리터럴을 사용한 점에 유의하세요.

main() 함수에서는 sizeof(arr)/sizeof(arr[0]) 연산으로 배열의 원소 개수를 구한 뒤, 이를 함수에 전달하여 최종 확률을 출력합니다. 이 알고리즘의 시간 복잡도는 O(1)로, 배열의 크기와 관계없이 일정한 시간 안에 결과를 얻을 수 있다는 장점이 있습니다.