[알고리즘]백준 10986: 나머지 합

처음에는 슬라이딩 윈도우 기법으로 풀었으나 이 경우 시간복잡도가 O(N^2)으로 N의 최대값이 10^6이기 때문에 시간초과가 발생했다.

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

public class Main {
    static int N,M;
    static int[] numbers;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //1. 입력
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        numbers = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) numbers[i] = Integer.parseInt(st.nextToken());
        //Arrays.sort(numbers);
        //System.out.println(Arrays.toString(numbers));

        //2. 1~N까지 반복
        answer = 0;
        for(int n=1; n<=N; n++){
            //System.out.println("n: "+n);
            int sum=0;
            for(int i=0; i<n; i++) sum+=numbers[i];
            if(sum%M==0) answer++;

            //System.out.println(sum);
            for(int i=n; i<N; i++){
                sum-=numbers[i-n];
                sum+=numbers[i];
                //System.out.println(sum);
                if(sum%M==0) answer++;
            }
        }

        //3. 출력
        System.out.println(answer);
    }
}

이를 개선하기 위해서 누적합을 사용해야 한다.

누적합

누적합 알고리즘은 배열의 특정 구간의 합을 효율적으로 계산하기 위한 방법으로, 미리 배열의 각 위치까지의 합을 계산해두고, 이를 이용해 원하는 구간 합을 빠르게 계산하는 것이다.

• 누적합 배열을 생성하는데 걸리는 시간: O(N)
• 구간 합을 계산하는데 걸리는 시간: O(1)

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

public class B10986_2 {
    static int N, M;
    static int[] arr;
    static long[] sumArr;

    public static void main(String[] args) throws IOException {
        //1. 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //2. 누적합
        int s = 0;
        sumArr = new long[M];
        for(int i=0; i<N; i++){
            s += arr[i];
            s = s % M;
            sumArr[s]++;
        }

        //3. 계산
        long answer = sumArr[0];
        for(int i=0; i<M; i++){
             answer += sumArr[i]*(sumArr[i]-1)/2;
        }
        System.out.println(answer);
    }
}

누적합을 이용하면 O(N^2) → O(N+M)으로 시간복잡도를 개선할 수 있다.

 

 

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