[BOJ] 백준 19951. 태상이의 훈련소 생활

문제

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

19951번: 태상이의 훈련소 생활

---

풀이

 누적합을 이용해야하는 문제입니다.

 

1 ≤ N ≤ 100,000 

1 ≤ M ≤ 100,000 

1 ≤ a ≤ b ≤ N

 

 입력값의 범위가 위와 같아서, 누적합을 이용하지 않고 배열을 일일이 연산할 경우에는 시간 복잡도가 O(N^2)으로 1초의 시간 제한을 넘어가게 됩니다. 

 

  그래서 누적합 배열에 모든 숫자를 넣는 것이 아니라, 처음과 끝만 기록합니다.

       for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int k = sc.nextInt();
            sum[st] +=k;
            sum[ed+1] -=k;
        }

		 ...
         
        //누적합 배열 구하기
        for(int i =1;i<=N;i++){
            sum[i] += sum[i-1];
        }

 여기서 중요한 것은 ed+1에 역으로 k를 빼주는 것입니다. 이것은 누적합 배열을 구성할 때에 끝 부분 이후로는 초기화를 시켜주어야 하기 때문입니다.

 

 예를 들어 {-1, -1, -1 ,0, 0, 0} 의 누적합 배열을 만든다고 생각해보겠습니다. 여기서 st = 0, ed = 3, k = -1일 것입니다.

 

그럼 초기 sum[] 배열은 {-1,0,0,1,0,0} 이 됩니다.

 

 st부터 ed까지 sum[i] 를 sum[i-1]을 더해 구해야하는데, 끝나는 지점+1에 k의 반대 부호 값이 없다면 {-1,-1,-1,-1,-1,-1} 로 배열이 끝나지 않습니다. 즉 끝나는 시점 이후로는 다시 원상복구를 시키기 위해서 부호의 반대 값을 더해, 이후부터는 0으로 채워줄 수 있게 합니다.

 

이렇게 만든 누적합 sum[] 누적합 배열을 ground[] 배열에 더해주면 정답을 구할 수 있습니다.

 

 

---

정답

import java.util.Scanner;

public class B19951_태상이의훈련소생활 {

    static int N,M;
    static int[] ground;
    static int[] sum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] ground = new int[N+1];
        int[] sum = new int[N+2];
        for(int i =1;i<N+1;i++){
            ground[i] = sc.nextInt();
        }
        for(int i = 0;i<M;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            int k = sc.nextInt();
            sum[st] +=k;
            sum[ed+1] -=k;
        }
        for(int i =1;i<=N;i++){
            sum[i] += sum[i-1];
            ground[i] +=sum[i];
        }
        for(int i =1;i<=N;i++){
            System.out.print(ground[i]+" ");
        }
    }
}