백준 10986 나머지 합 Java [누적합]

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

10986번: 나머지 합

 

 

규칙만 빨리 찾으면 쉬운(?) 문제지만, 규칙 찾는게 영 쉽진 않다

처음에 생각한 방식은 연속된 부분 구간의 합이니까 누적합을 생각해서 구해보았다

예제를 기준으로 1 3 6 7 9 이다

누적합을 구한 후 반복문으로 하나씩 탐색해가면서 앞에서 하나씩 빼가면서 나누어 떨어지는지 확인해보았다

이 방법대로하면 N^2의 시간복잡도로 시간초과이다

그래도 방법을 찾는데 어느정도 도움이 됐다

1은 나누어 떨어지지 않으니까 넘어가고

3은 나누어 떨어진다 3에서 1을 빼면 나누어 떨어지지 않는다

6은 나누어 떨어지고, 1을 빼면 나누어 떨어지지 않지만 3을 빼면 나누어 떨어진다

7은 1을 빼면 나누어 떨어지고 3과 6을 빼면 나누어 떨어지지 않는다

9는 3과 6을 빼면 나누어 떨어지고, 1과 7을 빼면 나누어 떨어지지 않는다

 

여기서 추가로 배열 가장 뒤에 2를 추가해보았다

(예제에는 3으로 나눈 나머지가 0인 경우와 1인 경우 밖에 없다)

11은 1, 3, 6, 7, 9 어느 숫자도 나누어 떨어지지 않는다

 

나머지를 기준으로 자신보다 앞쪽에 있으면서

같은 나머지를 가진 숫자가 있으면 나누어 떨어진다는 것을 확인했다

-> 자신보다 작은 인덱스면서 나머지가 같은 인덱스의 갯수만큼 나누어 떨어진다

추가적으로 나머지가 0인 3, 6, 9의 경우 나누어 떨어지므로 결과값에 추가적으로 넣는다

 

나머지들만 확인하면 되기 때문에 입력받을 때 M으로 나눈 나머지로 배열에 넣어줬다

 

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

public 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());
        st = new StringTokenizer(br.readLine());
        int[] sum = new int[N];
        long[] count = new long[M];
        long result = 0;
        sum[0] = Integer.parseInt(st.nextToken())%M;
        for (int n = 1; n < N; n++) {
            sum[n] += (Integer.parseInt(st.nextToken()) + sum[n-1])%M;
        }
        for (int n = 0; n < N; n++) {
            if (sum[n] == 0) result++;
            result += count[sum[n]]++;
        }
        System.out.println(result);
    }
}

 

결과값과 count 배열은 long 타입으로 만들었는데

M이 2이고 전부다 2의 배수인 경우 대략 N^2의 크기의 숫자가 들어와서 long타입으로 해야한다