[백준 / BOJ] 10986번 : 나머지 합 - JAVA

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

10986번: 나머지 합

나머지의 누적 합

이 문제에서 사용하는 건 나머지 값밖에 없기 때문에, 누적 합을 구하되 나머지 값만 누적하면 된다는 생각이 가장 먼저 들었다. 예제1과 같은 경우는 다음과 같이 진행되는 것이다.

// 예제 1
5 3
1 2 3 1 2

numbers : [1 2 3 1 2]
누적 합 : [1 3 6 7 9]
나머지의 누적 합 : [1 0 0 1 0]

나머지의 누적 합은 구했는데 여기에서 어떻게 구간 합을 구해볼 것인가? 일단 i부터 j까지 직접 돌려보는 것은 안된다. N값이 최대 10의 6승이기 때문에 O(N^2)으로는 시간 초과가 난다.

 

이 때 떠오른 것이 "나머지의 누적 합에서 값이 0인 경우 나누어 떨어진다"는 것이다. 생각의 흐름은 다음과 같다.

// 예제 1
5 3
1 2 3 1 2

나머지의 누적 합 : [1 0 0 1 0]

 

1. 0번째 ~ i번째 누적했을 때 나누어 떨어지는 것 : [1 0 0 1 0]
2. 0번째를 제외하고, 1번째 ~ i번째 누적했을 때 나누어 떨어지는 것 : 1 [0 0 1 0]
3. 1번째까지 제외하고, 2번째 ~ i번째 누적했을 때 나누어 떨어지는 것 : 1 0 [0 1 0]
4. 2번째까지 제외하고, 3번째 ~ i번째 누적했을 때 나누어 떨어지는 것 : 1 0 0 [1 0]
5. 3번째까지 제외하고, 4번째 ~ i번째 누적했을 때 나누어 떨어지는 것 : 1 0 0 1 [0]

이처럼, 직전에 제외한 것까지의 나머지와 같은 값을 가지고 있는 열은 나누어 떨어진다. 

 

하지만 직전에 제외한 값과 동일한지 또 for문으로 체크하다간 O(N * N)이 될 것이기 때문에, 나머지 값의 개수를 세고 앞에서부터 하나씩 제외할 때마다 개수에서도 하나씩 마이너스를 진행해주었다.

따라서 매번 직전에 제외된 나머지 값의 누적 합과 같은 수의 개수를 세고, total에 더해주었다.

 

전체 코드

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

// 시간 : 452ms
// 메모리 : 164048KB
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());
		
        int[] sum = new int[N + 1];
        int[] remain = new int[M];
		st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			int n = Integer.parseInt(st.nextToken()) % M;
            sum[i] = (sum[i - 1] + n) % M;
            remain[sum[i]]++;
		}
        
		remain[0]++;
		long total = 0l;
		int prev = 0;
		for (int i = 0; i < N; i++) {
			prev = sum[i];
			remain[prev]--;
			total += remain[prev];
		}
		System.out.println(total);
		
	}

}