나머지 합

문제

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

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 $A_1, A_2, ..., A_N$이 주어진다. (0 ≤ $A_i$ ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

문제 풀이

예제 입력1을 살펴보면 다음과 같다.

5 3
1 2 3 1 2

A = {1, 2, 3, 1, 2} 를 합 배열로 나타내면

S = {1, 3, 6, 7, 9} 이다.

(A + B) % C 는 ((A % C) + (B % C)) %C 와 같다. 이 말은 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

합 배열에서 주어진 수 M으로 각 각 나눈 나머지로 값을 바꿔준다.

S = {1 0 0 1 0};

이렇게 0으로 바뀌어진 수가 뜻하는 바는
(0,0) 부터 (i,j)까지의 합을 M으로 나누었을 때 0으로 나누어 떨어진다는 것이다.

S[1] 은 A[0] 부터 A[1] 까지의 합 (3) 을 M으로 나누어 떨어진 값이다.
S[2] 은 A[0] 부터 A[2] 까지의 합 (6) 을 M으로 나누어 떨어진 값이다.
S[4] 은 A[0] 부터 A[4] 까지의 합 (9) 을 M으로 나누어 떨어진 값이다.

그 후 나머지 값이 같은 합 배열의 2개의 원소를 뽑는 경우의 수를 더해주면 된다.

S[0]과 S[3]은 나머지 1로 동일하다. 원본 배열 A에서 확인해보면 A[1] 부터 A[3] 까지의 원소 
값 중 2개를 뽑는 모든 경우의 수를 구하면 되기 때문에 3C2 = 3`` 

S[2]과 S[4]은 나머지 0으로 동일하다. 원본 배열 A에서 확인해보면 A[3] 부터 A[4] 까지의 원소 
값 중 2개를 뽑는 모든 경우의 수를 구하면 되기 때문에 2C2 = 1

총 경우의 수는 3 + 3 + 1 = 7이라는 결과 값을 도출할 수 있다.

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

class 나머지합 {

    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());

        long count = 0;
        long[] mod = new long[M];
        long[] sumArr = new long[N + 1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {

            sumArr[i] = sumArr[i - 1] + Long.parseLong(st.nextToken());

            if(sumArr[i] % M == 0)
                count++;

            mod[(int) (sumArr[i] % M)]++;
        }

        for(int i = 0; i < M; i++){
            count += mod[i] * (mod[i] - 1) / 2;
        }

        System.out.println(count);
    }


}

회고

https://girawhale.tistory.com/125 블로그와 Do it! 알고리즘 코딩 테스트 자바편을 통해서 풀이 방법을 이해 할 수 있었다. 혼자 힘으로 풀어보려고 해도 답을 도출해 낼 수가 없었다. 아직 골드 문제를 풀기는 어렵기만하다