[백준] 10986번 나머지 합(java)

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

10986번: 나머지 합

누적합 문제이다.

 

핵심

이 문제는 연속한 합이 입력값 M으로 나누어지는 케이스를 구하는 것이다.

이를 각 배열의 합, 그때의 나머지를 구하면 아래와 같다.

 

index	0	1	2	3	4	5
arr[i]		1	2	3	1	2
sum[i]		1	3	6	7	9
sum[i]%M		1	0	0	1	0

이때 우선 나머지가 0인 곳은 이전까지의 합이라 생각할 수 있으며, 동시에 요구 조건에 부합한다. sum [i]% M ==0

나머지의 수가 0은 3개 1은 2개로 나와있다.

(sum [j]% M) - (sum [i-1]% M) == 0을 만족하는 경우인 3C2 + 2C2 도 포함해주어야 한다.

코드를 통해 알아보자.

 

정답 코드

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

class Main {
    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[] sum = new long[N + 1];
        long[] division = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            sum[i] += (sum[i - 1] + Integer.parseInt(st.nextToken())) % M;
            if (sum[i] == 0) count++;
            division[(int) sum[i]]++;

        }

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

        System.out.println(count);
    }
}

해설

위에 말한 그대로 코드로 표현한 것이다.

sum배열에는 누적합이 담겨있다.

division에는 그때 나머지값들이 들어있다.

각 타입이 int가 아닌 long으로 둔 이유는 값의 범위가 크기 때문에 오버플로우가 생길 것을 대비한 것이다.

누적합이 0인 순간에 count를 올리고, 각 나머지의 개수를 구하여 가능한 경우의 수를 모두 더해준다.

 

 

배운 점

누적합의 경우 단순하고 쉬워 보이지만,

이러한 아이디어를 생각해 내는 것이 쉽지 않다고 생각한다.

논리적인 사고능력을 길러야 할 것 같다.