C++에서 arr[i]와 arr[j]가 서로 나누어 떨어지는 쌍(i, j)의 개수 세기

N개의 요소로 구성된 배열 arr[]가 주어졌을 때, arr[i]가 arr[j]로 나누어 떨어지거나 arr[j]가 arr[i]로 나누어 떨어지면서 i ≠ j를 만족하는 모든 유효한 인덱스 쌍(i, j)의 개수를 구하는 것이 목표입니다.

이 문제는 두 개의 for 루프를 사용해 배열 arr[]를 순회하면서 각 쌍마다 i ≠ j일 때 arr[i] % arr[j] == 0 또는 arr[j] % arr[i] == 0인지 검사하는 방식으로 해결할 수 있습니다. 조건이 참이면 쌍의 개수를 1씩 증가시키면 됩니다.

예제로 이해하기

입력 − Arr[] = { 2, 4, 3, 6 }, N = 4

출력 − 유효한 쌍의 개수: 3

설명 − 유효한 쌍은 다음과 같습니다.

Arr[0] & Arr[1] → (2, 4) : 4 % 2 == 0, 0 != 1
Arr[0] & Arr[3] → (2, 6) : 6 % 2 == 0, 0 != 3
Arr[2] & Arr[3] → (3, 6) : 6 % 3 == 0, 2 != 3

입력 − Arr[] = { 2, 5, 7, 9, 11 }, N = 5

출력 − 유효한 쌍의 개수: 0

설명 − 어떤 수도 다른 수를 나누어 떨어지게 하지 못하므로 만들 수 있는 쌍이 없습니다.

접근 방식

임의의 정수로 초기화된 배열 Arr[]를 준비합니다.
배열 Arr[]의 길이를 저장할 변수 n을 선언합니다.
countPairs(int arr[], int n) 함수는 배열과 그 길이를 입력받아, 주어진 조건을 만족하는 유효한 쌍의 개수를 반환합니다.
두 개의 for 루프로 쌍을 이루는 각 요소를 순회합니다.
바깥쪽 루프는 0 ≤ i < n-1, 안쪽 루프는 i < j < n 범위로 실행합니다.
arr[i] % arr[j] == 0 또는 arr[j] % arr[i] == 0인지 검사하고, 둘 중 하나라도 참이면 카운트를 증가시킵니다.
모든 루프가 종료되면 count에는 유효한 쌍의 총 개수가 저장됩니다.
count 값을 결과로 반환합니다.

예제 코드

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

// 조건을 만족하는 쌍의 개수를 세는 함수
int countPairs(int arr[], int n){
    // 쌍의 개수
    int count = 0;
    for (int i = 0; i < n-1; i++){
        for (int j = i + 1; j < n; j++){
            // 한쪽이 다른 쪽으로 나누어 떨어지는 경우
            if(arr[i]%arr[j]==0 || arr[j]%arr[i]==0)
                { count++; }
        }
    }
    return count;
}
int main(){
    int Arr[] = { 2,3,4,5,6 };
    int len = sizeof(Arr) / sizeof(Arr[0]);
    cout << "Count of number of pairs : "<< countPairs(Arr, len);
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of number of pairs : 3

시간 복잡도

두 개의 루프를 중첩해 사용하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 커지면 실행 시간이 빠르게 증가하므로, 값의 범위가 제한적인 경우에는 각 수의 배수 개수를 빈도 배열로 미리 계산해 두는 방식으로 최적화할 수 있습니다.