[BaekJoon] 10986 나머지 합 (Java)

1.  문제 링크

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

2.  문제

요약

• 수 N개 $A_1, A_2, ..., A_N$이 주어질 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수, 즉 $A_i + ... + A_j$(i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 $10^6$보다 작거나 같은 N과 2보다 크거나 같고 $10^3$보다 작거나 같은 M이 주어지고 두 번째 줄에 0보다 크거나 같고 $10^9$보다 작거나 같은 N개의 수 $A_1, A_2, ..., A_N$이 주어집니다.
• 출력: 첫 번째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static long answer;
    static long[] prefixSum, count;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        prefixSum = new long[N + 1];
        count = new long[M];
        answer = 0;
        for(int idx = 1; idx <= N; idx++) {
            prefixSum[idx] = (prefixSum[idx - 1] + scanner.nextInt()) % M;
            if(prefixSum[idx] == 0) answer++;
            count[(int)prefixSum[idx]]++;
        }
    }

    static void solution() {
        for(int idx = 0; idx < M; idx++)
            answer += count[idx] * (count[idx] - 1) / 2;
        System.out.println(answer);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}