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

---

- 문제 핵심

1) (A + B) % C == ((A  % C) + (B % C)) % C

=> 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일

 

2) 구간 합 배열 S[i] - S[j]는 원본 배열의 j + 1부터 i까지의 구간 합

 

3) S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M == 0

=> 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i]와 S[j]가 같은 (i, j) 쌍을 찾으면 원본 배열에서 j + 1부터 i까지의 구간 합이 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 arr[] = new long[m];	// 나머지 인덱스 카운트 배열
		long sum[] = new long[n];	// 합 배열
		long result = 0;
		
		sum[0] = sc.nextInt();
		for (int i = 1; i < n; i++) {	// 합 배열
			sum[i] = sum[i - 1] + sc.nextInt();
		}
		
		
		for (int i = 0; i < n; i++) {
			int remainder = (int)(sum[i] % m);	// 나머지 구함
			
			// 0 ~ i까지의 구간 합 자체가 0일 때 정답에 더하기
			if (remainder == 0) {
				result++;
			}
			
			// 나머지가 같은 인덱스의 개수 카운팅
			arr[remainder]++;
		}
		
		for (int i = 0; i < m; i++) {
			if (arr[i] > 1) {
				// 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기	3C2 / 2C2
				result = result + (arr[i] * (arr[i] - 1) / 2);
			}
		}
		
		System.out.println(result);
		
		sc.close();
	}
}