[JAVA] 백준 10986

10986번: 나머지 합

문제

연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하시오.

풀이

이 문제는 나머지 연산은 묶어낼 수 있다는 점을 사용해야 한다.

합배열을 M으로 나눈 나머지 값을 계산한 배열을 계산한다.

여기서 나머지가 0이라는 의미는 주어진 배열 A[0] ~ A[i] 구간의 합이 M으로 나누어 떨어진다는 의미이다.

나머지 배열이 같은 값을 가지고 있다면 C[i] - C[j]는 0이 된다.

이 수식은 다음과 같이 볼 수 있다.

합 배열 S[i] - S[j]는 A[j] ~ A[i]구간의 합 배열이고 이 구간의 합 배열은 S[i] %M - S[j] % M = 0이 된다는 의미이다.

나머지 연산은 언제 계산하든지 상관 없기 때문에 나머지 연산 배열 C에서 같은 값을 꺼내 빼준다면 나머지는 0이 된다는 의미이다.

따라서

합 배열을 구하고 합 배열에 나머지 연산을 수행한 나머지 합 배열을 계산한다.

여기서 나머지 합 배열이 0이되는 구간을 카운트한다.

그런 다음 나머지 합 배열에서 같은 나머지를 갖는 값들에 대해서 $_nC_2$ 연산을 수행하면 카운트를 할 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
       Scanner sc = new Scanner(System.in);
       int N = sc.nextInt();
       int M = sc.nextInt();
       long[] S = new long[N];
       long[] C = new long[M];

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

결과