나머지 합

백준 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으로 나누어 떨어지는 구간의 개수를 출력한다.

풀이)
배열이 다음과 같다고 가정(N = 5)

1	2	3	1	2

우선은 0번째 부터 현재 위치까지 배열의 합으로 업데이트 한다.

1	3	6	7	9

주어진 int M으로 나눈다. 여기서는 M을 3으로 가정하겠다.

1	0	0	1	0

값이 0이라면 인덱스 0부터 해당 위치 까지 배열의 합은 M으로 나누어 떨어진다는 뜻이므로 결과에 0의 개수만큼 더한다.
동일한 결과값 두 개의 값이 만난다면(예를 들어 위 예제에서 index가 0과 3인 경우 나머지는 1로 동일. 따라서 index 1부터 3까지 부분 구간의 합은 M으로 나누어 떨어진다고 볼 수 있다.) 조건에 해당하므로 같은 값 두 개를 뽑는 경우의 수 만큼 결과에 더한다.

따라서 위 예제의 결과값은 3(0의 개수) + 3(0 두 개를 뽑는 경우의 수) + 1(1 두 개를 뽑는 경우의 수) = 7이다.

조합 공식
nCr = n!/(n-r)!r!
nC2 를 배열로 구한다고 가정하면(n값이 index번째 배열에 있다)
결과 += 배열[index] * (배열[index] - 1) / 2;라고 할 수 있다.

소스)

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

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());
		 
		 final int N = Integer.parseInt(st.nextToken());//배열의 길이
		 final int M = Integer.parseInt(st.nextToken());//나눠야 하는 값
		 int[] input = new int[N + 1];//배열
		 int[] mod = new int[M];//나머지 개수 배열
		 long result = 0;//return할 결과값_long으로 선언해야 한다
		 
		 for(int i = 0; i < M; i++) {//mod배열을 0으로 초기화
			 mod[i] = 0;
		 }
		 
		 st = new StringTokenizer(br.readLine());
		 for(int i = 1; i <= N; i++) {
			 input[i] = input[i - 1] + Integer.parseInt(st.nextToken());
			 input[i] %= M;
			 mod[input[i]]++;
		 }
		 
		 //값이 0일 때
		 result += mod[0];
		 //같은 값을 두 번 뽑는 경우의 수
		 for(int i = 0; i < M; i++)
			 if(mod[i] > 1)
				 result += (long)mod[i] * (mod[i] - 1) / 2; 
		 
		 System.out.print(result);
	}

}