[JAVA] 백준 (골드3) 10986번 나머지 합

링크

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

---

문제 설명

정답률 26.546%
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

---

입력 예제

• 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)
• 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10^9)

5 3
1 2 3 1 2

---

출력 예제

• 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

7

---

풀이

N의 최댓값이 $10^6$이므로 $10^6$만큼의 모든 구간 합을 구해야 한다. 우선 구간 합 배열을 이용하여 합 배열을 구한다.

long[] sum = new long[N];  //구간 합 배열
sum[0] = Long.parseLong(st.nextToken());
for (int i = 1; i < N; i++) {
    //S[i] = S[i - 1] + A[i]
    sum[i] = sum[i - 1] + Long.parseLong(st.nextToken());
}

i부터 j까지의 구간 합 중 M으로 나누어 떨어지는 개수를 구하는데 모든 경우를 생각하는 것도 N의 최댓값을 생각하면 초과가 날 것이다.

나머지 연산의 성질이 있는데 예를 들어 3으로 나눈 나머지를 구할 때
$(5 + 2) \% 3 = 7 \% 3 = 1$ 이다.
이때 각 숫자에 나머지 연산을 한 뒤 나머지 연산을 해도 결과는 같다.
$((5 \% 3) + (2 \% 3)) \% 3 = (2 + 2) \% 3 = 1$

이 성질을 이용하면 i+1부터 j까지의 구간 합은 $S[j] - S[i]$ 이고
$S[j] \% M$과 $S[i] \% M$의 값이 같다면
$(S[j] - S[i]) \% M$의 값은 0이다. (0을 나눈 나머지는 0)

즉, 구간 합 배열의 원소를 각각 M으로 나눈 나머지로 업데이트하고 같은 원소를 카운트하면 된다. 카운트할때는 N개 중에 2개를 뽑는 경우의 수이니 조합을 이용한다.
$nC_2 = n! * (n-1)! /2$

그리고 업데이트한 구간 합 배열이 0인 원소는 0부터 i까지의 구간 합을 M으로 나눈 나머지가 0이라는 것이므로 따로 카운트한다.

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());  //수의 개수
        int M = Integer.parseInt(st.nextToken());  //제수 (divisor)
        st = new StringTokenizer(br.readLine());

        long[] sum = new long[N];  //구간 합 배열
        sum[0] = Long.parseLong(st.nextToken());
        for (int i = 1; i < N; i++) {
            //S[i] = S[i - 1] + A[i]
            sum[i] = sum[i - 1] + Long.parseLong(st.nextToken());
        }

        long answer = 0;
        long[] count = new long[M];  //같은 나머지 카운트
        for (int i = 0; i < N; i++) {
            //합 배열을 나눈 나머지가 0이면 정답++
            int remainder = (int) (sum[i] % M);
            if (remainder == 0) {
                answer++;
            }
            //나머지가 0이 아닐 때 카운트
            count[remainder]++;
        }

        for (int i = 0; i < M; i++) {
            //같은 나머지의 개수에서 2가지를 뽑는 경우의 수를 정답에 더한다.
            if (count[i] > 1) {
                answer += count[i] * (count[i] - 1) / 2;
            }
        }

        System.out.println(answer);
    }
}