[BOJ] 10986. 나머지 합

[작성일]

• 2022-03-13

[분류]

• 누적합
• 조합
  
  
  

[문제링크]

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

[요구사항]

• 부분합이 M으로 나누어 떨어지는 개수를 구하라.
  
  
  

[풀이]

우리가 구해야 할 것은 부분합이 M으로 나누어 떨어지는 경우이다.
즉 (sum[j] - sum[i-1])%M = 0이 되는 경우이다.
분배법칙에 의해서 sum[j]%M = sum[i-1]%M이 되는 경우로 볼 수 있다.

나머지 개수를 저장하는 배열 count에 누적합을 M으로 나눴을 때 나머지 개수를 구해준다.

누적합을 구할 때에 M으로 나누어 떨어질 경우 count[0]++이 되는데, 다 구하고 나서 정답에 더해준다. 2개의 쌍을 지을 필요 없이 그 자체 누적합이 답이 되는 경우이기 때문이다.

이제, 그 count[k]가 있다고 하면, 그것은 곧 M으로 나눴을 때 나머지가 같은 개수의 모임이 된다고 볼 수 있다.
그럼 그 중 2개씩 쌍을 지어주면 sum[j]%M = sum[i-1]%M의 경우라고 할 수 있다.
조합의 공식 (n*(n-1))/2에 따라서 구해서 모두 더해주면 정답이 된다.

[코드]

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

class Main {
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        long ans = 0;
        long sum = 0;
        long[] count = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            // 누적합 구하기
            sum = sum + Long.parseLong(st.nextToken());
            count[(int) (sum % M)]++;
        }

        ans += count[0];
        // (sum[j] - sum[i]) % M = 0 인 구간을 찾아야한다.
        // 즉, sum[j]%M = sum[i]%M 이 되는 모든 경우의 수를 더해주면 된다.
        for (int i = 0; i < M; i++) {
            // 구간합의 나머지(count)가 같은 거 2개를 뽑아서 다 더하는 경우의 수를 ans에 더해주면 된다.
            // 그걸 조합 공식으로 하면 (n*(n-1))/2이기 때문에 아래와 같은 식을 쓴다.
            ans += (count[i]*(count[i]-1))/2;
        }
        System.out.println(ans);
    }
}