[Baekjoon Online Judge] 19951. 태상이의 훈련소 생활 (Java)

핵심

N과 M이 최대 100,000이다.

완전 탐색 시, 최악의 경우 시간복잡도가 O(NM)이므로 시간초과이다.

 

이와 같이 큰 범위를 다룰 때, 시간을 줄이기 위한 방법의 하나로 누적합이 있다.

누적합
이름에서 유추할 수 있듯이 값을 계속해서 쌓는 것이다.
e.g. [1, 2, 3, 4, 5] 의 누적합을 원소로 하는 배열은 [1, 3, 6, 10, 15]
기존 배열의 인덱스 2~4 범위의 합을 구하려면, 가장 단순한 방법은 해당 범위를 순회하며 일일이 합하는 것이다. 누적합 배열 acc를 이용하면 acc[4] - acc[1]로 O(1)에 계산할 수 있다.

 

이 문제의 경우는 누적합 아이디어를 사용하면 해결할 수 있다.

 

우선 상태를 기록할 새로운 배열 acc를 만든다.

조교 1이 2~4번 칸에 흙을 3만큼 쌓으라고 했다면, acc[2] += 3, acc[5] -= 3을 한다.

[0, 3, 0, 0, -3, ...]

이 배열에 대한 누적합을 구하면 [0, 3, 3, 3, 0, 0, 0, ...] 이 된다. 즉, 각 위치에 대해 쌓아야 할 흙의 양이 된다.

 

다음에 조교 2가 3~5번 칸에 흙을 1만큼 쌓으라고 했다면, acc[3] += 1, acc[6] -= 1을 한다.

[0, 3, 1, 0, -3, -1, ...]

 

이제 이 배열에 대한 누적합을 구하면, 모든 조교가 각 위치에 쌓으라고 흙의 양이 나온다.

[0, 3, 4, 4, 1, 0, ...]

 

 

 

Code (Java)

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

class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        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());

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

        int[] acc = new int[N + 2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            acc[a] += k;
            acc[b + 1] -= k;
        }

        int sum = 0;
        for (int i = 1; i <= N; i++) {
            sum += acc[i];
            sb.append(arr[i] + sum).append(' ');
        }

        System.out.println(sb);
    }
}