[JAVA] 나머지 합 구하기 - 백준 10986번

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

처음에는 2차원 배열을 만들어서 문제를 풀어보려고 하였다.
하지만 문제의 조건중 N의 범위가 1 <= N <= 10^6 이기 때문에 최악의 경우에는 메모리 제한인 256MB를 초과해 버릴 수 있다.

때문에 누적합을 사용하여 해결하였다.

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(input.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] array = new int[n];
        st = new StringTokenizer(input.readLine());
        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        long answer =0;
        long[] S = new long[n];
        int[] C = new int[m];
        S[0] = array[0];
        for(int i = 1; i < n; i++){
            S[i] = S[i-1] + array[i];
        }
        for(int i = 0; i<n; i++){
            int remain = (int) (S[i] % m);
            if(remain == 0){
                answer++;
            }
            C[remain]++;
        }

        for(int i = 0; i<m; i++){
            if(C[i]>1){
                answer += ((long) C[i] * (C[i]-1) / 2);
            }
        }
        System.out.println(answer);
    }
}

코드 설명

for(int i = 1; i < n; i++){
    S[i] = S[i-1] + array[i];
}

입력값을 받은 후 각 인덱스까지의 누적합을 계산한다.

for(int i = 0; i<n; i++){
    int remain = (int) (S[i] % m);
    if(remain == 0){
       answer++;
    }
    C[remain]++;
}

각 인덱스까지의 누적합을 m으로 나눈 나머지를 구하고, 나머지가 0 이라면 나누어 떨어진 것이므로 anwer를 증가시킨다.

또한 C[remain]++의 경우 누적합의 나머지를 인덱스로 하여 해당 경우의 수를 증가시키는 부분인데.

이 부분이 필요한 이유는 다음과 같다.

누적합 S[i], S[j]가 있을 때, S[i] % m == S[j] % m이라면 두 누적합 구간 사이의 차이인 S[j] - S[i]는 M으로 나누어 떨어진다.

즉 C[remain]의 값이 2 이상이라면 M으로 나누어 떨어지는 (i, j) 쌍이 존재하기 때문에 문제에서 요구하는 조건에 부합한다.

이후 배열 C의 값을 순회하면서 2이상인 경우 중에서 2개를 뽑는 경우의 수를 더해주면 된다.

for(int i = 0; i<m; i++){  
    if(C[i]>1){  
        answer += ((long) C[i] * (C[i]-1) / 2);  
    }  
}

 

마지막으로 answer가 int타입이라면 오버플로가 발생할 수 있으니 long타입을 사용하자