[백준] 10986 나머지 합

 

__💡구간합 (PrefixSum)__
구간 합 응용 구현 문제 __
https://www.acmicpc.net/problem/10986

 

Question

문제

수 N개 A1, A2, ..., AN이 주어진다. 
이때, 연속된 부분 구간의 합이 M으로 
나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 
M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

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

Tag

수학, 구간합 (누적합)

---

Answer (./Main.java)

합배열을 만든 후 해당 합배열의 나머지가 0인 값들에 대하여 결과를 ++
나머지가 같은 요소들이 2개 이상 있을경우 해당 요소들을 이용해야한다

나머지가 같은 요소가  2개 이상일 경우 해당 요소들의 index 를 이용해서
C[i] - C[i-1] 구간을 구하면 결국 나머지가 0이 되므로 이 구간도 정답에 포함된다.

즉 나머지가 같은 요소들의 개수를 구한 후 그 것들 중 2개를 조합하면 나머지가 0인 구간생성됨
조합공식을 이용해 2개를 뽑고 해당 값을 result 에 추가해주면 된다.
풀이뿐 아니라 주어진 조건에서도 long 과 int 형을 잘 구분해주어야 함

메모리(kb)	시간 (ms)	시간복잡도
120768	516	$O(n)$

 

package CodingTest.Algorithm.PrefixSum.G3_10986;

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        long[] S = new long[N];
        S[0] = Integer.parseInt(st2.nextToken());
        for (int i = 1; i < N; i++) {
            S[i] = S[i - 1] + Integer.parseInt(st2.nextToken());
        }
        long result = 0;

        // 나머지가 같은애들 개수를 세기 위한 배열
        // 나머지는 나누는 수 보다 작으므로 배열 크기는 M
        long[] C = new long[M];
        // 3으로 나눈 나머지 계산
        for (int i = 0; i < N; i++) {
            int remain = (int) (S[i] % M);
            // 일단 나머지가 0 인건 답이니까 추가
            if (remain ==0) result++;
            // 나머지가 같은애들 새로운
            C[remain]++;
        }

        for (int i = 0; i < M; i++) {
            // 나머지가 같은개 2개 이상일떄
            if (C[i] > 1) {
                // 해당 나머지의 개수중에서 2개를 뽑는다 C(n, 2)
                // 이거는 곧 n * (n-1) /2
                result += C[i] * (C[i] - 1) / 2;
            }
        }
        System.out.println(result);
    }
}