백준 10986: 나머지 합 구하기(java)

문제

---

풀이

 

모듈러(modulo) 연산의 성질을 알고 있어야 시간 제한 내에 해결할 수 있는 문제다.

 

\(A\;mod\;B=R\)

 

에서 \(mod\)를 모듈러 연산자라 하고, 이때 \(R\)은 \(A\)를 \(B\) 로 나눈 나머지이다. 자바, 파이썬 등에서는 % 연산자로 표기한다.

 

모듈러 연산에서 분배 법칙이 성립하는데, 이 중 1번, 2번 공식을 풀이에 이용할 것이다.

1. \((a\;mod\;n+b\;mod\;n)\;mod\;n=(a+b)\;mod\;n\)
2. \((a\;mod\;n-b\;mod\;n)\;mod\;n=(a-b)\;mod\;n\)
3. \((a\;mod\;n\times{b\;mod\;n})\;mod\;n=(a\times{b})\;mod\;n\)

입력받은 N개의 정수를 저장할 arr[N]과, arr[i-1] + arr[i](1 ≤ i ≤ N)의 부분 구간 합을 저장할 sum[N]배열을 사용한다.

 

인덱스 i부터 j 까지의 구간 합은 \(sum\big[j\big]-sum\big[i-1\big]\)이므로, i~j 구간 합이 M으로 나누어 떨어진다는 것은

\((sum\big[j\big]-sum\big[i-1\big])\;mod\;M=0\)임을 의미한다.

이때 모듈러 분배 법칙의 2번 공식을 적용하면,

\((sum\big[j\big]-sum\big[i-1\big])\;mod\;M=(sum\big[j\big]\;mod\;M-sum\big[i-1\big]\;mod\;M)\;mod\;M=0\) 이다.

 

이를 통해 M으로 나누어 떨어지거나, M으로 나눈 나머지가 같은 sum[] 원소들을 찾아야 함을 알 수 있다.

 

전체 코드

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

public 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());
		
		st=new StringTokenizer(br.readLine());
		
		int[] A=new int[N];
		
		for(int i=0; i<N; i++) {
			A[i]=Integer.parseInt(st.nextToken());
		}
		
		long[] sum=new long[N];
		sum[0]=A[0];
		
		long[] remainder=new long[M];
		long count=0;
		
		for(int i=1; i<N; i++) {
			sum[i]=sum[i-1]+A[i];
		}
		for(int i=0; i<N; i++) {
			sum[i]%=M;
			
			if(sum[i]==0) {
				count++;
			}
			
			remainder[(int) sum[i]]++;
		}
		
		for(int i=0; i<M; i++) {
			if(remainder[i]>1) {
				 count+=(remainder[i]*(remainder[i]-1)/2);
			}
		}
		
		System.out.println(count);
	}
}