[백준] 10986번(Java)

📖 나머지 합

[ 문제 ]
수 N개 $A_1$, $A_2$, ..., $A_N$이 주어진다. 이때, 연속된 부분 구간의 합이 $M$으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, $A_i$ + ... + $A_j$ ($i$ ≤ $j$) 의 합이 $M$으로 나누어 떨어지는 ($i$, $j$) 쌍의 개수를 구해야 한다.
첫째 줄에 N과 M이 주어진다. ($1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3$)
둘째 줄에 N개의 수 $A_1, A_2, ..., A_N$이 주어진다. ($0 ≤ A_i ≤ 10^9)$

💡풀이

• 이 문제 어려웠다.
• 일반적인 누적합 계산 로직으로 특정 위치까지의 누적합을 구한 뒤, 두 구간의 차이를 $M$으로 나눴을 때 나누어 떨어지는지를 확인해 개수를 구했더니 시간 초과가 나왔다.
• 위치 별 누적합을 구하되, 각 위치까지의 나머지의 누적합을 구해 계산한 뒤, 동일한 누적합을 갖는 위치들끼리 몇 가지 조합이 나오는지 계산하면 된다.
• 가령, 1의 나머지를 갖는 위치가 총 4개가 나온다면, 4개 중 중복되지 않는 2개를 선택하는 방법을 통해 계산하면 된다. ( $_4C_2$ )

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

public class bj10986 {
    static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[] cul = new long[N];
        int[] mod = new int[M];

        long res = 0;
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N; i ++){
            int t = Integer.parseInt(st.nextToken());
            if(i == 0) cul[i] = t;
            else cul[i] = t + cul[i-1];

            mod[(int)(cul[i] % M)] ++;
            if(cul[i]% M == 0) res ++;
        }

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

    }
}

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