C++로 구현하는 합이 K로 나누어지는 처음 N개의 자연수 쌍의 개수 구하기

두 개의 숫자 N과 K가 주어졌을 때, 1부터 N까지의 자연수 중에서 서로 다른 두 수의 합이 K로 나누어지는 쌍(pair)의 개수를 세는 문제입니다. 예시를 통해 살펴보겠습니다.

입력

N = 3
K = 2

출력

1

합이 K로 나누어지는 쌍은 (1, 3) 하나뿐입니다. 두 수의 합이 4이며, 이는 2로 나누어떨어지기 때문입니다. 반면 (1, 2)의 합은 3, (2, 3)의 합은 5로 2로 나누어지지 않습니다.

알고리즘

• N과 K를 초기화합니다.
• 1부터 N까지의 자연수를 생성하여 배열에 저장합니다.
• 카운트 변수를 0으로 초기화합니다.
• 두 개의 반복문을 사용해 배열에서 가능한 모든 쌍을 탐색합니다.
  • 각 쌍의 합을 계산합니다.
  • 쌍의 합이 K로 나누어떨어지면 카운트를 1 증가시킵니다.
• 최종 카운트를 반환합니다.

이 방식은 모든 가능한 쌍을 하나씩 검사하는 브루트 포스(Brute Force) 기법으로, 시간 복잡도는 O(N²)입니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

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

int getPairsCount(vector<int> arr, int N, int K) {
    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int sum = arr[i] + arr[j];
            if (sum % K == 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> arr;
    int N = 10, K = 5;
    for (int i = 1; i <= N; i++) {
        arr.push_back(i);
    }
    cout << getPairsCount(arr, N, K) << endl;
    return 0;
}

실행 결과

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

9

N = 10, K = 5인 경우, 1부터 10까지의 수 중에서 합이 5의 배수가 되는 쌍은 총 9개입니다. 예를 들어 (1, 4), (1, 9), (2, 3), (2, 8), (5, 10) 등이 해당되며, 각 쌍의 합은 모두 5 또는 10처럼 5로 나누어떨어집니다.

만약 N이 매우 큰 경우에는 나머지 분포(모듈로 연산)를 활용하면 O(N + K) 시간 복잡도로 최적화할 수 있으므로, 효율성이 중요한 상황에서는 참고하시기 바랍니다.