[JAVA][백준][G3] 10986번 나머지 합

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

📒 문제

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

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

 

시간 제한 / 메모리 제한

 1초 / 256MB

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

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

 

입출력 예

# 입력1
5 3
1 2 3 1 2

# 출력1
7

 

알고리즘 분류

• 수학
• 누적 합

---

💻 소스코드

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

public class Main{
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());

		 int N = Integer.parseInt(st.nextToken()); // 배열의 개수
		 int M = Integer.parseInt(st.nextToken()); // 나눌 수

		 long result = 0;
		 
		 // 합 배열 생성
		 long[] arr= new long[N+1];
		 st = new StringTokenizer(br.readLine());
		 arr[1] =  Integer.parseInt(st.nextToken());
		 for (int i = 2; i <= N; i++) {
			  arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
		 }

		 // 배열 원소에 % M
		 long[] C = new long[M];
		 for (int i = 1; i <= N; i++) {
			  long r = arr[i] % M;
			  if(r == 0) result++;
			  C[(int) r]++;
		 }

		 for (int i = 0; i < M; i++) {
			  if(C[i] > 1) result += (C[i] * (C[i] - 1) / 2);
		 }

		 bw.write(String.valueOf(result));
	
		bw.flush();
		bw.close();
    }   
}

📝 풀이

[JAVA][알고리즘] 구간 합

 

[알고리즘] 나누기 연산의 분배 법칙