백준 10986 [나머지 합]

문제

수 n개 A1, A2, ..., An이 주어질때 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구하시오.

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

10986번: 나머지 합

---

 이 문제는 누적합의 개념을 알고 있어야 풀 수 있는 문제이다.

 누적합은 주어지는 수를 배열에 저장할 때 A1, A2, A3, ... An으로 저장하는게 아니라 A1,  A1+A2,  A1+A2+A3, ... 이런식으로 계속 더하면서 저장하는 방법이다. 누적합이 좋은 점은 누적합을 저장한 배열을 S라 할때 주어진 수들의 i ~ j번째의 연속된 구간의 합을 하나하나 더할 필요 없이 S[j] - S[i - 1]로 구할 수 있다.

 

    S[i - 1] = A1 + A2 + ... + Ai-1

    S[j]      = A1 + A2 + ... + Ai-1 + Ai + ... + Aj

    S[j] - S[i - 1] = Ai + ... Aj

 

 하지만 이번 문제를 누적합을 이용해 모든 경우의 수를 다 m으로 나머지 연산해 풀려 하면 시간 초과가 발생한다. 그래서 모든 경우의 수를 조사하기보단 S배열의 값을 이용하여 좀 더 빠른 알고리즘을 짜야한다. 새로운 방법을 이해하기 위해 다음을 이해해보자.

 

i	0	1	2	3	4
A[i]	1	2	3	1	2
S[i]	1	3	6	7	9
M[i]	1	0	0	1	0

 다음 표는 백준에서 주어진 첫번째 테스트케이스로 만들었다.

(주어진 수는 순서대로 1, 2, 3, 1, 2 이렇게 5개이며 m = 3이다)

 

 A[i]는 주어진 수, S[i]는 누적합, M[i]는 누적합을 나머지 m으로 나눈 값이다. 여기서 M[i] == 0인 i = 1, 2, 4일때는 m으로 나누어지는 연속된 부분 구간합이라 볼 수 있다. 이렇게 3개의 경우의 수를 찾았는데 나머지 경우의 수는 어떻게 찾아야 할까?

 위에서 얘기했던 내용 중 S[j] - S[i - 1]로 i ~ j의 연속된 부분 구간합을 구할 수 있다고 했던것을 기억하면 나머지 경우의 수를 찾을 수 있다. S[j] - S[i -1]이 m으로 나누어 떨어지면 이를 m으로 나누어 떨어지는 연속된 부분 구간합의 하나로 볼 수 있다는 말이다. 따라서 M[i]가 동일한 S[i]끼리 빼면 된다.

 

 위의 표에서는 M[i]가 다음과 같이 분포되어있다.

 

    M[i] = 0인 경우 : 3개 (i = 1, 2, 4)

    M[i] = 1인 경우 : 2개 (i = 0, 3) 

 

 이를 이용하여 같은 M[i]값을 갖는 S끼리 빼주는 경우의 수를 모두 구해주면 나머지 경우의 수를 전부 찾을 수 있다.

 

    M[i]가 0인 경우는 3개이므로 3개중 2개를 고르는 경우의 수 3C2 = 3

    M[i]가 1인 경우는 2개이므로 2개중 2개를 고르는 경우의 수 2C2 = 1

 

따라서 전체 경우의 수는 3 + 3 + 1 = 7이 된다.

 

이를 코드를 통해 공부해 보자.

 

import java.io.*;
import java.util.*;
class Main {
    static long Comb(long n){
        if (n < 2)
            return 0;
        else
            return n * (n - 1) / 2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long[] S = new long[n];
        int[] M = new int[n];
        int[] C = new int[m];
        for (int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            if (i == 0)
                S[i] = num;
            else
                S[i] = S[i - 1] + num;
            M[i] = (int)(S[i] % m);
            C[M[i]]++;
        }
        long sum = C[0];
        for (int i = 0; i < m; i++)
            sum += Comb(C[i]);
        System.out.println(sum);
    }
}

 위에서 설명한 내용과 같다. 여기서 새로운 점은 배열 C인데 C는 다음과 같은 역할을 한다.

 

    C[i] : M에 저장된 i의 개수

 

즉 위에서 든 예시에서 C의 역할을 대입해보면 

   

    C[0] = 2

    C[1] = 3 

  

이렇게 값이 저장이 된다.

따라서 값을 입력받으면서 S, M, C를 완성하고 sum에 우선 M[0]을 넣어주고 C의 요소들을 Comb함수에 대입한 값들을 sum에 추가로 더해주면 답이 나온다.