[백준] 19951번. 태상이의 훈련소 생활(JAVA)

문제

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

---

풀이(19분)

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

public class Main {

    // 1-based IDX

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

        st = new StringTokenizer(br.readLine());

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

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

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

        int sum = 0;

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++){
            sum += order[i];
            sb.append(sum+height[i]).append(" ");
        }

        System.out.println(sb);

    }
}

---

문제 풀이 전략

 

 

📌 누적합(Difference Array) 기법을 이용한 구간 연산 최적화

✨ 문제 접근

처음 문제를 접했을 때 누구나 같은 고민을 한다.

"구간에 전부 더하고 빼야 하는데, 하나하나 다 하면 시간 초과가 나지 않을까?"\

 

후에 백준 10713과 유사하다고 생각했다.

---

🧠 해결 아이디어

구간 연산을 빠르게 하기 위한 방법은 누적합 배열(Difference Array) 를 사용하는 것이다.

💡 누적합 배열은, 직접 값을 더하지 않고
“어디에서 시작해서 어디까지 얼마를 더해야 하는지”만을 기록해두는 방식이다.

---

🔢 예제 시뮬레이션

5 3
0 0 0 0 0
1 2 1
2 4 -2
3 5 5

📊 직접 계산한 결과 

 

1️⃣ STEP 1)

0

0

0

0

0

<연병장의 높이>

 

0

0

0

0

0

<누적합 높이>

 

여기서 누적합 높이가 뭘까? 어떤 인덱스에서 몇을 더해줘야 할지를 저장해두는 배열이다.

잘 이해가 안 되겠지만 따라와보자.

첫 조교의 지시는 1번과 2번 칸에 +1씩 하라는 것이다.

1

1

0

0

0

<연병장의 높이>

 

1

0

-1

0

0

<누적합 높이>

 

위와 같은 상태가 될 것이다.

연병장의 높이는 지금 즉시 지시를 이행한 것이다.

누적합 높이는 1~2번칸에 +1이기 때문에 시작점인 1번 칸에 +1을, 끝 점인 2번+1인 3번 칸에 -1(1 * -1)을 해둔 것이다.

일단 그냥 그렇다고 생각하자.

---

2️⃣ STEP 2)

두번째 조교의 지시는 2~4에 -2이다.

1

-1

-2

-2

0

<연병장의 높이>

 

1

-2

-1

0

+2

<누적합 높이>

 

위와 같은 상태가 될 것이다.

연병장의 높이는 지금 즉시 지시를 이행한 것이다.

누적합 높이는 2~4번칸에 -2이기 때문에 시작점인 2번 칸에 -2를, 끝 점인 4번+1인 5번 칸에 +2(-2 * -1)을 해둔 것이다.

일단 그냥 그렇다고 생각하자.

---

3️⃣ STEP 3)

세번째 조교의 지시는 3~5에 +5이다.

1

-1

3

3

5

<연병장의 높이>

 

1

-2

4

0

+2

<누적합 높이>

 

위와 같은 상태가 될 것이다.

연병장의 높이는 지금 즉시 지시를 이행한 것이다.

누적합 높이는 3~5번칸에 +5이기 때문에 시작점인 3번 칸에 +5를, 끝 점인 5번+1인 6번 칸이 없기에 무시한다.

일단 그냥 그렇다고 생각하자.

---

🔄 누적합을 기반으로 원래 배열 복원

0

0

0

0

0

 

다시 초기 배열을 가져오고, int sum = 0으로 시작한다.

모든 인덱스마다  누적합의 값을 sum에 더한 뒤 연병장의 초기 높이에 더해보자.

1. idx = 0; sum += 1 -> sum ==1 ,  연병장[0] = 0 + 1;

2. idx = 1; sum += -2 -> sum == -1; 연병장[1] = 0 - 1;

3. idx = 2; sum += 4 -> sum == 3; 연병장[2] = 0 + 3;

4. idx = 3; sum += 0 -> sum == 3 연병장[3] = 0 + 3;

5. idx = 4; sum += 2 -> sum == 5; 연병장[4] = 0 + 5;

 

직접 계산한 결과와 완전히 동일하다!