C++로 x로 나누어 떨어지는 이진 배열 접두사 개수 구하기

이 튜토리얼에서는 이진 배열의 접두사 중 주어진 값 x로 나누어 떨어지는 것의 개수를 구하는 프로그램을 살펴보겠습니다.

문제에서는 0과 1로만 구성된 이진 배열과 정수 값 x가 주어집니다. 우리의 목표는 배열의 각 위치까지의 접두사(앞부분)를 하나의 이진수로 해석했을 때, 그 값이 x로 나누어 떨어지는 경우의 수를 세는 것입니다.

문제 이해하기

예를 들어, 배열 {1, 0, 1, 0, 1, 1, 0}과 x = 2가 주어졌다고 가정해 보겠습니다. 각 인덱스까지의 접두사를 이진수로 변환하면 다음과 같습니다.

1 → 1 (나누어 떨어지지 않음)
10 → 2 (✓ 나누어 떨어짐)
101 → 5 (나누어 떨어지지 않음)
1010 → 10 (✓ 나누어 떨어짐)
10101 → 21 (나누어 떨어지지 않음)
101011 → 43 (나누어 떨어지지 않음)
1010110 → 86 (✓ 나누어 떨어짐)

조건을 만족하는 접두사는 총 3개이므로 결과값은 3이 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 기존 접두사 값에 새 비트를 추가할 때는 number * 2 + arr[i] 공식으로 값을 갱신할 수 있습니다. 이렇게 하면 매번 처음부터 이진수를 다시 계산하지 않고도 현재 접두사의 십진수 값을 O(1)에 효율적으로 유지할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// x로 나누어 떨어지는 접두사를 가진
// 원소의 개수를 세는 함수
int count_divx(int arr[], int n, int x){
    int number = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        // 현재 접두사의 십진수 값 갱신
        number = number * 2 + arr[i];
        // 조건을 만족하면 카운트 증가
        if ((number % x == 0))
            count += 1;
    }
    return count;
}
int main(){
    int arr[] = { 1, 0, 1, 0, 1, 1, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    cout << count_divx(arr, n, x);
    return 0;
}

출력 결과

코드 설명

count_divx() 함수는 배열, 배열의 크기 n, 나눌 값 x를 매개변수로 받습니다.
반복문을 돌며 number = number * 2 + arr[i]를 통해 현재 위치까지의 접두사를 십진수로 변환합니다.
number % x == 0 조건을 만족하면 카운트를 1 증가시킵니다.
모든 원소를 확인한 후 최종 카운트를 반환합니다.

시간 복잡도

배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가 공간은 상수 수준인 O(1)입니다. 다만 배열의 길이가 매우 길면 접두사 값이 자료형 범위를 초과할 수 있으므로, 실제 환경에서는 long long을 사용하거나 모듈러 연산을 활용하는 것이 안전합니다.