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

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

---

풀이 과정

이 문제는 1년전에 풀었었는데 지금 다시 보니 생각이 안나서 풀어보기로 했다.

문제를 보면 흙파기를 명령이 들어왔을 때 바로바로 하는게 아니라 한번에 모아뒀다가 파겠다는건데

명령마다 구간이 다르기때문에

어디는 3만큼 파야될수도 있도 어디는 5만큼 파야될 수도 있고, 덮기도 해야해서 각 칸마다 변화량이 다르다는 것이 문제이다.

 

그래서 명령이 들어오는 그대로 모든칸에 변화를 줘버리면 결국 계속 파내고 덮고 하는거나 마찬가지인셈이라서

한번에 끝내야한다는 생각은 문제를 읽자마자 바로 든다.

 

이걸 어떻게 n만큼 기록을 안하고 최대한 o(1)로 해결할까?

변화한 값을 매 칸마다 기록하는게 아니라 시작과 끝만 적용되도록 기록하면 된다.

 

예시를 보면

첫번째 명령에서 1~5까지 3만큼 파내는데

1번칸에 -3을 기록하면 그 뒤는 전부 -3을 하겠다는 뜻이된다.(변화량이 -3)

그런데 우리는 5번칸까지만 -3을 해야되기때문에 그 뒤로(6번칸부터)는 +3을 해주면 결국 0이 된다.

그림으로 보면

 

이렇게 되면 한번의 명령에 기록은 2번하니깐 O(2)가 되고 마지막에 변화량을 기록한 배열을 쭉 돌면서 

변화량을 정리하고 작업을 하면 된다.

---

풀이 코드

// 연병장 크기 N, 조교 수 M
// 누적합
// 범위 연산 수치를 기록하는 배열 delta
// 모든 칸에 대한 변화량을 기록하지 않고 처음과 끝만 기록한다
// ex) 2번부터 7번까지 -2 연산을 한다고 하면, 2번부터 끝까지 -2를 한 후, 7번 + 1부터 끝까지 +2를 하는 것과 같다.
// delta 배열에 시작부분에 k, 끝 부분 다음부터 -k를 기록한다.
// 이후 resultDelta 배열을 만들어 delta 배열을 누적합한 다음 기존 연병장에 변화량을 계산하여 출력한다.
// 누적합이 되는 이유 : 앞의 변화량이 뒤의 변화량에도 계속 누적되어 계산되기 때문

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

public class Main {

    public static void main(String[] args) throws Exception{
        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());   // 조교 수

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

        int[] delta = 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());

            delta[a] += k;
            delta[b + 1] -= k;
        }

        int[] resultDelta = new int[N + 1];
        for (int i = 1; i < resultDelta.length; i++) {
            resultDelta[i] = resultDelta[i - 1] + delta[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < arr.length; i++) {
            sb.append(arr[i] + resultDelta[i]).append(" ");
        }
        System.out.println(sb);
    }

}

 

---

나는 이걸 한번 풀어봤기때문에 예전의 기억을 되짚으면서 풀었지만

일반적으로 쉽게 접할 수 있는 누적합 문제와는 느낌이 다르다.

일반적으로 누적합이라고 하면 처음부터 끝까지 쭉 누적합을 계산하는데

이 문제는 그렇게 하면 효율성이 떨어지게 되는 문제.

 

그렇게 하면 안된다는 건 알지만 그래서 어떻게 기록을 해야 효과적일까를 알아차리는게 쉽지 않은 문제였다.(나한테는...)