[백준] 나머지 합(10986)

https://www.acmicpc.net/problem/10986

이 문제는 연속된 부분의 구간 합이 M으로 나누어 떨어지는 구간의 개수가 몇 개인지 카운트하는 문제이다.

우리가 학습한 구간 합 공식을 사용하되, 중간에 나누어 떨어지는 구간이 몇 개 있는지도 같이 확인해야하는 것이 핵심이다.

나머지 정리에 의해 성립하는 아래 공식을 생각해보자.
(A + B) % C = ((A % C) + (B % C)) % C

이를 구간 합에 적용하면 아래와 같다.
S[i] % M과 S[j] % M이 같다면 (S[j] - S[i]) % M은 0이다.

📌 쉬운 이해를 위한 비유

원형으로 되어있는 길에서 두 사람이 각각 S[i]와 S[j] 만큼 걸었다고 가정해보자.

M = 10이라고 할때, S[i] = 25, S[j] = 45라면
S[i] % M = 25 % 10 = 5
S[j] % M = 45 % 10 = 5

(S[j] - S[i]) % M = (45 - 25) % 10 = 0

따라서 S[i] % M과 S[j] % M이 같다면 (S[j] - S[i]) % M은 0이다.

---

다시 말해 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i, j)의 쌍을 찾으면 원본 배열에서 i+1부터 j까지 구간합이 M으로 나누어 떨어진다는 것을 파악할 수 있다.

따라서 문제풀이 방법은 다음과 같다.

1. 합 배열 구하기
2. 합 배열의 모든 값을 M으로 나머지 연산 진행
3. 나머지가 0인 경우 카운트
4. 나머지 배열의 원소 개수가 2 이상이면 나머지가 i인 구간 중 2개를 선택하는 경우의 수를 더하기
   => 원소 개수가 2개 이상이어야 한 쌍을 찾을 수 있음
   => 조합을 이용하여 계산하는 공식을 사용함
   => $_nC_2 = n*(n-1) / 2$

Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

# 원본 배열
num_arr = list(map(int, input().split()))

# 합 배열
sum_arr = [0] * N

# M으로 나누어 떨어진 나머지의 개수를 담는 배열
# 이후 나머지 개수를 세기 위해 사용함
c_arr = [0] * M

sum_arr[0] = num_arr[0] # 0번째 원소는 0으로 초기화

# 합 배열 저장
for i in range(1, N):
    sum_arr[i] = sum_arr[i - 1] + num_arr[i]

answer = 0

# 합 배열에서 M으로 나눈 나머지 계산
for j in range(N):
    remainder = sum_arr[j] % M
    
    # 만약 나머지가 0이라면 나누어 떨어진다는 의미이므로
    if remainder == 0:
        answer += 1 # 카운트 1 증가

    # 나머지가 같은 인덱스의 개수 값 카운트
    # 예를 들어 나머지가 1이면 c_arr[1] += 1이 됨
    c_arr[remainder] += 1

for i in range(M):
    # 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수 구하기
    if c_arr[i] > 1:
        answer += (c_arr[i] * (c_arr[i] - 1) // 2)

print(answer)

Java

import java.util.Scanner;

public class P_10986 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        long[] A = new long[N + 1];
        long[] S = new long[N + 1];

        for (int i = 1; i <= N; i++) {
            A[i] = sc.nextLong();
        }

        for (int i = 1; i <= N; i++) {
            S[i] = S[i - 1] +  A[i];
        }

        long[] C = new long[M];
        long answer = 0;

        for (int i = 1; i <= N; i++) {
            int remainder = (int) (S[i] % M);

            if (remainder == 0)
                answer++;

            C[remainder]++;
        }

        for (int i = 0; i < M; i++) {
            if (C[i] > 1) {
                answer += (C[i] * (C[i] - 1) / 2);
            }
        }
        System.out.println(answer);
    }
}

자바의 경우 배열에 들어갈 수 있는 $A_i$의 최댓값이 $10^9$으로 매우 크다. 따라서 int 대신 long 자료형으로 사용해서 해결해야 한다.