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

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

10986번: 나머지 합

 

이 문제는 이중반복문으로 풀려하면 시간초과가 나는 문제로,

어느정도 수학적 접근이 필요하다.

 

먼저 문제분석을 하자면

 

연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구하면 된다.

 

전체 구간의 범위 n이 매우크기 때문에 단순하게 접근해서는 풀 수 없다.

 

이 문제를 풀기 위한 아이디어는 

 

첫번째 수부터 n번째 수까지의 누적합을 구하되

 

그 과정에서 현재까지의 누적합에 대해 m을 나눈 나머지가 같은 누적합끼리 그룹을 지어주어야 한다.

 

문제에서 예제로 나온

 

5 3

1 2 3 1 2를 예시로 설명하자면,

 

번호	1	2	3	4	5
숫자	1	2	3	1	2

 

1번째 수부터 누적합을 순차적으로 구해보겠다.

 

1번째 숫자일땐, 다음과 같이 표현할수 있다.

 

	1	2	3	4	5
숫자	1	2	3	1	2
누적합	1

 

나머지	0	1	2
개수	0	1	0

 

두번째 누적합의 경우

1 + 2 = 3 이므로

3으로 나눈 나머지는 0이다.

따라서 나머지가 0인 그룹에 하나가 추가된다.

	1	2	3	4	5
숫자	1	2	3	1	2
누적합	1	1 + 2

 

나머지	0	1	2
개수	1	1	0

 

이 일련의 과정을 끝내면 다음과 같은 표를 작성할 수 있다.

 

	1	2	3	4	5
숫자	1	2	3	1	2
누적합	1	1 + 2	1 + 2 + 3	1 + 2 + 3 + 1	1 + 2 + 3 + 1 + 2

나머지	0	1	2
개수	3	2	0

 

 

정리하면 나머지그룹 0은 1+2, 1+2+3, 1+2+3+1+2

나머지 그룹 1은 1, 1+2+3+1 이 들어가 있는 것이다.

 

이때 나머지 그룹 0에 해당하는 누적합들은 이미 나머지가 0이므로 기본적을 구간의 개수는 3개부터 시작한다.

 

그리고 각 그룹에서 2개의 누적합을 골라 차를 구했을 경우에 나머지는 0임을 알 수 있다.

 

즉, 나머지 그룹 1에 해당하는 누적합인 1과 1+2+3+1을 골랐을 경우

1+2+3+1 - 1의 나머지는 0이므로 이런 경우에도 누적합의 구간에 포함이 되는것을 알 수 있다.

 

 

따라서 그룹의 개수가 k 인 경우,

현재 그룹의 누적합 구간의 수를 T 라고 한다면,

$$T =  \frac{k(k - 1)}{2}$$

 

인 것을 알 수 있다.

 

그럼 예제에 대한 답을 낸다면,

 

0인 나머지 그룹의수 : 3

1인 나머지 그룹의수 : 2

7 = 3 + 3(3 - 1)/2 + 2(2 - 1)/2 이므로

7개의 구간임을 알수 있다.

 

실제로 누적합 구간을 구한다면,

1 , 1 + 2 , 1 + 2 + 3, 2 + 3 + 1, 3 , 1 + 2 + 3 + 1 + 2 , 3 + 2 + 1

다음과 같은 7개 구간임을 알 수 있다.

 

따라서 이를 코드로 작성하게 되면 다음과 같이 작성할 수 있겠다.

 

package boj4;

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

public class Boj10986 {
	
	/*
	 * 제출 完
	 */
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(in.readLine()," ");
		
		in.close();
		
		long[] mod = new long[m];
		long sum = 0;
		for(int i = 0; i < n; i++) {
			sum += Long.parseLong(st.nextToken());
			int modIdx = (int) (sum%m);
			mod[modIdx]++;
		}
		
		long ans = mod[0];
		
		for(int i = 0; i < m; i++) {
			if(mod[i] > 1) {
				ans += mod[i] * (mod[i] - 1) >> 1;
			}
		}
		
		System.out.print(ans);
	}

}

 

예제에 대한 답도 잘 출력하고 있음을 확인할 수 있다.