C/C++로 배열 원소 곱을 n으로 나눈 나머지 구하기

배열 곱셈 문제에서는 주어진 배열의 모든 원소를 곱한 후, 그 결과를 특정 숫자 n으로 나눈 나머지(remainder)를 구해야 합니다. 먼저 예제를 통해 문제를 살펴보겠습니다.

입력: arr[] = { 12, 35, 69, 74, 165, 54 };
      N = 47
출력: 14

문제 설명

배열이 {12, 35, 69, 74, 165, 54}와 같을 때, 모든 원소를 곱하면 (12 * 35 * 69 * 74 * 165 * 54) = 19107673200이 됩니다. 이 값을 47로 나누면 나머지는 14입니다.

접근 방법

가장 직관적인 방법은 모든 수를 먼저 곱한 뒤 n으로 나눈 나머지를 구하는 것입니다. 하지만 이 방식에는 치명적인 문제가 있습니다. 배열의 크기가 커져 곱셈 결과가 2^64 범위를 초과하면 오버플로우가 발생하여 잘못된 답을 얻게 됩니다.

이를 해결하려면 모듈러 연산의 성질을 활용해야 합니다. 즉, 다음 식이 성립한다는 점을 이용합니다.

(a * b) % n = ((a % n) * (b % n)) % n

각 원소를 곱할 때마다 중간 결과에 계속 n으로 나눈 나머지 연산을 적용하면, 값이 커지는 것을 막아 오버플로우 없이 정확한 결과를 구할 수 있습니다.

구현 예제 (C)

#include <stdio.h>
int main() {
    int arr[] = { 12, 35, 69, 74, 165, 54};
    int len = 6;
    int n = 47 ;
    int mul = 1;
    for (int i = 0; i < len; i++)
        mul = (mul * (arr[i] % n)) % n;
    printf("the remainder is %d", (mul%n));
    return 0;
}

실행 결과

the remainder is 14

위 코드에서는 반복문 안에서 매번 (mul * (arr[i] % n)) % n을 계산함으로써 중간 곱셈 값이 항상 n보다 작게 유지됩니다. 이 덕분에 배열의 길이가 아무리 길어도 데이터 타입의 범위를 초과하지 않고 올바른 나머지를 안정적으로 구할 수 있습니다.