C++에서 배열 전체 곱셈 결과를 n으로 나눈 나머지 구하기

개요

n개의 원소로 이루어진 배열 A가 있다고 가정해 보겠습니다. 우리가 해야 할 일은 배열의 모든 숫자를 곱한 뒤, 그 결과를 n으로 나눴을 때의 나머지를 구하는 것입니다.

예를 들어 A = [100, 10, 5, 25, 35, 14]이고 n = 11이라면, 출력값은 9입니다. 즉, 100 * 10 * 5 * 25 * 35 * 14 mod 11 = 9가 되는 것입니다.

접근 방법

배열의 모든 값을 먼저 곱하면 수가 기하급수적으로 커져 정수 오버플로우(overflow)가 발생할 수 있습니다. 따라서 다음과 같은 순서로 계산해야 합니다.

1. 각 숫자에 대해 n으로 나눈 나머지를 먼저 구합니다.
2. 구한 나머지를 현재까지의 누적 결과에 곱합니다.
3. 곱셈 직후 다시 한 번 n으로 나눈 나머지를 구하여 오버플로우를 방지합니다.

나머지 연산의 성질 (a * b) mod n = ((a mod n) * (b mod n)) mod n을 활용하면 중간 결과를 항상 n보다 작게 유지할 수 있어 안전하게 계산할 수 있습니다.

예제 코드

#include<iostream>
#include<algorithm>
using namespace std;
int getRemainder(int a[], int size, int n) {
    int mul = 1;
    for(int i = 0; i<size; i++){
        mul = (mul * (a[i] % n)) % n;
    }
    return mul % n;
}
int main() {
    int arr[] = {100, 10, 5, 25, 35, 14};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 11;
    cout << "The remainder is: " << getRemainder(arr, size, n);
}

실행 결과

The remainder is: 9

코드 설명

getRemainder 함수는 누적곱 변수 mul을 1로 초기화한 후, 배열의 각 원소를 순회하며 해당 원소를 n으로 나눈 나머지를 mul에 곱하고 다시 n으로 나눈 나머지를 저장합니다. 반복문이 끝나면 최종적으로 mul % n을 반환합니다. main 함수에서는 예시 배열 {100, 10, 5, 25, 35, 14}와 n = 11을 사용해 결과를 출력하며, 실행 결과로 9가 출력되는 것을 확인할 수 있습니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.