[Java] 백준 10986 나머지 합 - 구간 합(3)

백준 10986 나머지 합
문제

수 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)

출력

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

---

제출

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		long [] S = new long[N];
		long [] C = new long[M];
		long answer = 0;
		
		S[0] = sc.nextInt();
		for (int i = 1; i <N; i++) {
			S[i] = S[i-1] + sc.nextInt();
		}
		
		for (int i = 0; i<N; i++) {
			int remainder = (int) (S[i]%M);	//나머지 연산
			if (remainder == 0) answer++;	//0~i까지의 구간 합 자체가 0일 때 answer++
			C[remainder]++;		//나머지가 같은 인덱스의 개수 카운팅				
		}
		for (int i = 0; i < M; i++) {
			if (C[i] > 1) {
				//나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기
				answer = answer + (C[i] * (C[i] -1) / 2);
			}
		}
		System.out.println(answer);
	}
}

 

예제

5 3
1 2 3 1 2

결과

백준 10986 나머지 합

 

10986번: 나머지 합