Baekjoon(백준) 10986 번 나머지 합

●문제 출처

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

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

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

<입력>
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

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

●코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        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());   
        long result = 0;                            
        long[] S = new long[N + 1];                 
        long[] cnt = new long[M];                   

      
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            S[i] = (S[i - 1] + Integer.parseInt(st.nextToken())) % M;
            
            if(S[i] == 0) {
                result++;
            }
          
            cnt[(int) S[i]]++;
        }

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

●느낀 점
다른 블로그 보고 참고하였다..
S[] 에는 전에 숫자와 차이를 구하여 배열에 넣고 만약 M으로 나누어 떨어지면 result를 증가 시켜주고 cnt[]에 M으로 나눴을 때 나머지가 몇개 인지 계산하여 cnt[나머지]에 증가시켜준다.

다음으로 cnt[i]가 2이상이면
result += (cnt[i] * (cnt[i]-1)/2); 를 한다

이 식이 나온 이유는
n C r : n개 중에서 r개를 뽑는 모든 경우의 수
를 계산하기 위해서 이다. 즉 N개 중 2개를 뽑는 확률이다.

S[] 가 예를 들어 01001 이렇게 되어있으면
나머지가 '1'인 위치인 거 끼리 계산하면 M으로 나누어 떨이진다.
그래서 2C2 1이고 나머지가 '0' 인 위치를 계산하면 3C2 3이다.(+ S[]가 0인 개수)
따라서, 총 7개가 된다.

이해하는데는 어려움이 없어지만, 골드3 문제라 막상 코드를 짜라고 하면 못짤 거 같다...ㅠㅠ