[백준] 10986. 나머지 합 (JAVA)

➕ 나머지 합

 

수학적 사고가 약간은 필요한 누적 합 문제(?)

 

---

문제

수 N개 A₁, A₂, ..., A_N이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10⁶, 2 ≤ M ≤ 10³)

둘째 줄에 N개의 수 A₁, A₂, ..., A_N이 주어진다. (0 ≤ Ai ≤ 10⁹)

 

출력

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

 

---

🔑 IDEA

sum[i]를 i번 째 수 까지의 누적 합이라 할 때,

i+1부터 j까지 구간의 누적합은 sum[j] - sum[i]로 나타낼 수 있다. 

따라서 (sum[j] - sum[i]) % M == 0 인 구간을 찾아야 한다. 

 

(sum[j] - sum[i]) % M == 0 에서 분배법칙을 통해

sum[j]%M - sum[i]%M == 0 의 식을 도출할 수 있고

결국 sum[i] % M == sum[j] % M 인 구간 i~j의 수를 세면 된다. 

 

따라서, 우리는 같은 나머지를 가진 누적합 중 2개를 순서없이 뽑는 경우의 수를 세면 된다. 

이를 위해 0번 째 수 부터 N-1번 째 수 까지 누적합 sum을 구해가며

그 때의 나머지를 계산해 remainder[sum%M]++ 해준다.

 

모든 누적합에 대한 나머지 수를 저장했으면 

각 나머지 수에서 2개를 뽑는 경우의 수를 모두 더하면 된다. 

 

 

💡 나의 풀이

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

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());

		int sum = 0;
		int[] remainder = new int[M];

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			sum += Integer.parseInt(st.nextToken()) % M;
			remainder[sum%M]++;
		}

		long ans = remainder[0];
		for(int i=0; i<M; i++) {
			int n = remainder[i];
			ans += (long)n*(n-1)/2;
		}
		System.out.println(ans);
	}
} 

 

 

---

 

10986번: 나머지 합