[Baekjoon 백준] 10986 나머지 합 - Java

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

---

1. 변수 선언

2. 수열 구간 합 배열, 구간 합 나머지 배열 선언

3. 구간 합 계산

4. 구간 합 나머지 계산

5. 경우의 수 판단하여 최종 값에 더하기

 

public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("src/baekjoon/code10986"));
		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 rm = (int) (S[i] % M);
			//0~i 구간 합의 나머지가 0일 때 정답 count
			if(rm == 0) answer++; 
			//나머지가 같은 인덱스 개수 count
			C[rm]++;
		}
		
		for(int i=0; i<M; i++) {
			if(C[i]>1) {
				//나머지가 같은 인덱스 중 2가지를 뽑는 경우의 수 더하기
				answer = answer + (C[i]*(C[i]-1)/2);
			}
		}
		System.out.println(answer);
	}

 

 

• 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
• 구간 합 배열을 이용한 식 S[i] - S[j]는 원본 배열의 j + 1 부터 i까지의 구간 합이다.
• S[i] % M 의 값과 S[j] % M의 값이 같다면 (S[i]-S[j]) % M은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[i]와 S[j]가 같은 (i,j)쌍을 찾으면 원본 배열에서 j + 1 부터 i 까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.