C++로 배열에서 등차수열(AP) 부분 수열 개수 구하기

정수 요소로 이루어진 배열 arr[]가 주어졌을 때, 우리의 목표는 arr[] 안에서 만들 수 있는 등차수열(Arithmetic Progression, AP) 부분 수열의 개수를 세는 것입니다. 배열에 들어갈 수 있는 요소의 값 범위는 [1, 1000000]입니다.

여기서 중요한 점은 빈 수열이나 원소가 하나뿐인 수열도 등차수열로 간주하여 개수에 포함한다는 사실입니다.

예제로 이해하기

예시 1

입력 - arr[] = {1,2,3}

출력 - 배열에서 등차수열(AP) 부분 수열의 개수: 8

설명 - 다음 부분 수열들이 등차수열을 이룹니다.

{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

예시 2

입력 - arr[] = {2,4,5,8}

출력 - 배열에서 등차수열(AP) 부분 수열의 개수: 12

설명 - 다음 부분 수열들이 등차수열을 이룹니다.

{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, {5,8}, {2,5,8}

프로그램에 적용된 접근 방식

빈 수열도 하나의 등차수열로 취급합니다.
원소가 하나뿐인 수열 역시 등차수열입니다.
배열을 한 번 순회하여 최댓값(max_val)과 최솟값(min_val)을 구합니다. 모든 등차수열 부분 수열의 공차는 [min_val - max_val, max_val - min_val] 범위 안에 존재하게 됩니다.
각 공차별로 동적 계획법(Dynamic Programming)을 적용해 부분 수열을 찾고, 그 개수를 arr_2[size]에 저장합니다.
길이가 2 이상인 부분 수열의 개수는 공차가 D일 때 arr_2[i] - 1 값들의 합으로 구할 수 있습니다.
점화식은 arr_2[i] = 1 + Σ arr_2[j]입니다. 단, j < i이면서 arr[j] + D = arr[i]를 만족하는 j들에 대한 합입니다.
연산 속도를 높이기 위해 arr[j] + D = arr[i](j < i) 조건을 만족하는 arr_2[j]의 합을 미리 arr_3[max_size]에 누적해 둡니다.

알고리즘 상세 단계

정수 배열 arr[]를 입력받습니다.
함수 AP_subsequence(int arr[], int size)는 입력 배열을 받아 해당 배열 속 등차수열 부분 수열의 개수를 반환합니다.
초기 count 값을 0으로 설정합니다.
부분 수열 개수를 저장할 arr_2[size], 합계를 저장할 arr_3[max_size]와 함께 max_val, min_val 변수를 준비합니다.
for 반복문으로 arr[]를 순회하며 최댓값과 최솟값을 찾아 저장합니다.
원소 하나짜리 등차수열과 빈 등차수열까지 포함하기 위해 count를 size + 1로 초기화합니다.
가능한 공차의 양 끝값을 diff_max = max_val - min_val, diff_min = min_val - max_val로 계산합니다.
j = 0부터 j < size까지 반복하면서 다음을 수행합니다.
arr_2[j]를 1로 설정합니다.
arr[j] - i가 1 이상 1000000 이하인 경우 arr_2[j] += arr_3[arr[j] - i]로 갱신합니다.
count에 arr_2[j] - 1을 더합니다.
누적합을 arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j] 형태로 업데이트합니다.
모든 과정이 끝나면 count를 결과로 반환합니다.

예제 코드

#include<bits/stdc++.h>

using namespace std;
#define max_size 10000

int AP_subsequence(int arr[], int size) {
    int count = 0;
    int max_val = INT_MAX;
    int min_val = INT_MIN;
    int arr_2[size];
    int arr_3[max_size];

    for (int i = 0; i < size; i++) {
        max_val = min(max_val, arr[i]);
        min_val = max(min_val, arr[i]);
    }
    count = size + 1;
    int diff_max = max_val - min_val;
    int diff_min = min_val - max_val;
    for (int i = diff_max; i <= diff_min; i++) {
        memset(arr_3, 0, sizeof arr_3);
        for (int j = 0; j < size; j++) {
            arr_2[j] = 1;
            if (arr[j] - i >= 1) {
                if (arr[j] - i <= 1000000) {
                    arr_2[j] += arr_3[arr[j] - i];
                }
            }
            count += arr_2[j] - 1;
            arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
        }
    }
    return count;
}

int main() {
    int arr[] = {1,1,6,7,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
    return 0;
}

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

출력

Count of AP (Arithmetic Progression) Subsequences in an array are: 17

이 알고리즘은 가능한 모든 공차에 대해 배열을 한 번씩 훑는 구조이므로, 배열의 크기를 n, 값의 범위를 d라고 할 때 시간 복잡도는 O(n × d)입니다. 공간 복잡도는 부분 수열 개수를 저장하는 arr_2와 누적합을 저장하는 arr_3를 위해 O(max_size)만큼 추가로 필요합니다.