[BOJ] 10986 나머지 합 - JAVA

1. 문제

10986번: 나머지 합

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

---

2. 풀이

(arr[j] - arr[i])%M = 0

arr[j]%M-arr[i]%M = 0

arr[j]%M = arr[i]%M

따라서, M으로 나눈 나머지가 같은 것들의 조합을 구하면 된다. nC2 = (n*(n-1))/2

나머지를 remainder 배열에 저장해두고, answer을 remainder[0]으로 초기화한다. i==j가 가능하기 때문에, 수 하나로 M으로 나눠떨어지는 수의 개수를 미리 더해야하기 때문이다.

remainder 배열을 하나씩 살펴보면서 2 이상일 때 조합 식을 계산해 answer에 더한다.

출력한다.

import java.io.*;
import java.util.*;

public class BOJ_10986_나머지합 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N =Integer.parseInt(st.nextToken());
      int M =Integer.parseInt(st.nextToken());
      int[] arr = new int[N+1];
      long[] remainder = new long[M];
      st = new StringTokenizer(in.readLine());
      for(int i=1;i<=N;i++) {
         arr[i] = (arr[i-1]+Integer.parseInt(st.nextToken())%M)%M;
         remainder[arr[i]]++;
      }

      //조합
      long answer = remainder[0];
      for(int i=0;i<M;i++){
         if(remainder[i]<2) continue;
         answer += (remainder[i]*(remainder[i]-1)/2);
      }

      System.out.println(answer);
   }
}

---

3. 결과

처음에 곧이곧대로 풀었다가 시간초과났다.