[문제풀이] B10986 나머지합

나머지합

---

  🪅 입력범위를 보고서 결과값이 int 범위(2147483647)를 넘어서는지를 예측할 수 있는가
  🪅 구간합을 구할 때 누적합을 구할 수 있는가
  🪅 누적합을 구할 때 패딩을 넣어줄 수 있는가
  🪅 (S[i] - S[j]) % M == 0, 분배법칙을 이용해 문제를 해결할 수 있는가 => S[i] % M == S[j] % M
  🪅 쌍을 구할 때 Combination을 이용할 수 있는가 => nC2 = n(n-1)/2

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

public class B10986_나머지합_이우엽 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(token.nextToken());
        int M = Integer.parseInt(token.nextToken());
        long[] arr = new long[N+1];
        long[] S = new long[N+1];

        token = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i < N+1; i++) {
            arr[i] = Integer.parseInt(token.nextToken());
        }
//        System.out.println(Arrays.toString(arr));

        long[] restCnt = new long[M];
        for(int i = 1; i < N+1; i++) {
            S[i] = (S[i-1] + arr[i]) % M;
            restCnt[(int)S[i]]++;
        }
//        System.out.println(Arrays.toString(S));
//        System.out.println(Arrays.toString(restCnt));

        long result = restCnt[0];
        for(int i = 0; i < M; i++) { // M은 최대 10^9까지 올 수 있고
            result += restCnt[i]*(restCnt[i]-1)/2; // 나머지는 최대 10^9-1까지 나올 수 있다. 이 수를 곱하면 int값을 훨씬 넘어선다
        }

        System.out.println(result);
    }
}

💡 문제 접근 과정
결국 구간합 % M == 0이 되는 i, j 쌍을 구하는 문제이다.
구간합 = 누적합[i] - 누적합[j]이고,
분배법칙에 의해 정리하면 누적합[i] % M == 누적합[j] % M이 된다.
입력예에서 누적합을 M으로 나눈 나머지(패딩포함, 인덱스0)는 [0, 1, 0, 0, 1, 0]이 된다.
즉, 3개의 0중에서 인덱스가 다른 2개를 뽑는 경우의 수 3C2와
2개의 1중에서 인덱스가 다른 2개를 뽑는 경우의 수는 2C2를 더하면 4가 되고
애초부터 누적합의 나머지가 0이 되었다는 것은 문제의 조건을 만족하니(0,2) (0,3) (0,5)
이 3개를 더하면 7개가 된다.