005. 나머지 합(백준10986)

문제

문제 분석하기

제한 시간 1초 : 1억번의 연산안에 끝나야한다...!

$1<= N <= 10^6$, $2 <= M <= 10^3$
$10^6$ 개의 수에 대해 모든 구간 합을 구해 M 으로 나누어 떨어지는 구간 합의 개수를 구해야한다.
딱 봐도 1초안에는 무리데스...구간 합 배열 을 이용해야겠다는 생각이 들어야한다.

위 문제를 풀기위한 아이디어를 생각해보자 💡

합 배열 :
$S[i] = S[i-1] + A[i]$

구간 합 :
$S[ j ] - S[ i -1 ] = ( i, j )$ (i 부터 j 까지의 구간 합)

구간합 % M = 0 (구간 합이 M 으로 나누어 떨어진다면?)

수학적으로 정리해보면 아래와 같다.

$(S[ i ] - S[ j -1 ])\ \%\ M = 0$
(i 부터 j 까지의 구간 합이 M 으로 나누어 떨어진다.)

$(S[ i ]\ \%\ M) - (S[ j-1 ]\ \%\ M) = 0$
$(S[ i ]\ \%\ M) = (S[ j-1 ]\ \%\ M)$
즉, 구간 합 배열의 원소를 M 으로 나눈 나머지로 업데이트하고 원소의 값이 같은 (i, j)쌍을 찾으면 원본배열에서
i 부터 j 까지의 구간 합이 M 으로 나누어 떨어진다는 것을 알 수 있다.

손으로 풀어보기

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

1. 구간 합 공식을 사용해 (0, j) 까지의 구간 합 중 M 으로 나누어 떨어지는 수 구하기

들어온 예제를 이용해 합 배열을 구해 각 원소들을 M 으로 나누어주자
합 배열 : $S[i] = S[i-1] + A[i]$

index	0	1	2	3	4	5
$A[i]$	1	2	3	1	2
$S[i]$	1	3	6	7	9
$S[i]\ \%\ M$	1	0	0	1	0

(0, j) 까지의 구간 합 중 M 으로 나누어 떨어지는 수는 원소의 값이 0인 개수이다. + 3

2. (i, j) 일때의 M 으로 나누어 떨어지는 수 구하기

0부터 시작할 경우를 제외하고 1, 2, 3 부터 시작해 구간의 합이 M 으로 나누어 떨어질 경우도 더해줘야 한다.

변경된 합 배열($S[i]\ \%\ M$)에서 원소 값이 같은 인덱스의 개수 즉, 나머지 값이 같은 합 배열의 개수를 카운트한다.
1이 2개, 0이 3개 -> 같은 2개의 원소를 뽑는 모든 경우의 수를 구해 정답에 더하면 된다. (1하고 0뽑으면 어떻게해? 이 경우 랜덤한 두 수를 뽑는것이 아닌 상황이므로 상관없다.)

x개의 수 중 y개의 수를 뽑을 경우의 수 :
$x \times (x-1)\div y$

$_{2}\mathrm{C}_{2}$ -> 2개의 수 중 2개의 수를 뽑을 경우의 수 = +1
$2 \times (2-1)\div2$

$_{3}\mathrm{C}_{2}$ -> 3개의 수 중 2개의 수를 뽑을 경우의 수 = +3
$3 \times (3-1)\div2$

슈도코드 작성하기

S 입력 받기
M 입력 받기
S 선언하기
C 선언하기(같은 나머지의 인덱스를 카운트)
for(int i=1; i<=N; i++) {
	S\[i] = S\[i-1] + A\[0 ~ N]
}
for(int i=0; i<N; i++) {
	mod = S\[i] % M;
	if(mod == 0) 정답++;
	C\[mod] += 1;
}
for(int i=0; i<M; i++) {
	C\[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수
}

코드 구현하기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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( ) );

		// N 입력 받기
		int num = Integer.parseInt( st.nextToken() );
		// M 입력 받기
		int mod = Integer.parseInt( st.nextToken() );

		// 합 배열 선언
		long[] sumArr = new long[num];
		// 같은 나머지 그룹화를 위한 배열 선언
		long[] modArr = new long[mod];
		// result 선언
		long result = 0;

		// 합 배열 초기화
		st = new StringTokenizer( br.readLine() );
		sumArr[ 0 ] = Integer.parseInt( st.nextToken() );
		for ( int i = 1; i < num; i++ ) {
			sumArr[ i ] = sumArr[ i - 1 ] + Integer.parseInt( st.nextToken() );
		}

		// 합 배열의 모든 원소에 %M 연산
		for ( int i = 0; i < num; i++ ) {
			int temp = ( int )(sumArr[i] % mod);
			// 0~i 까지의 합이 0일 때
			if ( temp == 0  )
				result++;
			modArr[ temp ]++; // 나머지가 같을 때
		}

		for ( int i = 0; i < mod; i++ ) {
			// 나머지가 같은 원소 중 2개를 뽑는 경우의 수
			result += modArr[ i ] * ( modArr[ i ] - 1 ) / 2;
		}
		bw.write( result + "\n" );
		bw.flush();
	}

} // end