문제 설명

연병장은 1번부터 N번까지 일렬로 이루어진 칸이다.
각 칸에는 높이가 존재한다.

조교들은 다음과 같은 명령을 내린다.

[a, b] 구간에 k만큼 더하거나 빼라

• k ≥ 0 → 흙을 덮는다
• k < 0 → 흙을 파낸다

모든 명령을 수행한 뒤
각 칸의 최종 높이를 구하는 문제이다.

---

입력

첫째 줄

N M

둘째 줄

초기 높이

다음 M줄

a b k

조건

1 ≤ N, M ≤ 100,000

---

출력

최종 높이를 출력

---

입력 예시

10 3
1 2 3 4 5 -1 -2 -3 -4 -5
1 5 -3
6 10 5
2 7 2

출력 예시

-2 1 2 3 4 6 5 2 1 0

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

구간 업데이트를 빠르게 처리

---

왜 어려운가

단순하게 구현하면

[a, b] 구간을 매번 직접 업데이트

→ O(N × M)

최대

100,000 × 100,000 = 10^10

→ 시간초과

---

해결 방법

차분 배열 (Difference Array)

을 사용한다.

---

내가 작성한 코드

코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] origin = new int[N + 1];

        for (int i = 1; i <= N; i++)
            origin[i] = sc.nextInt();

        int[] delta = new int[N + 2];

        while (M-- > 0) {

            int a = sc.nextInt();
            int b = sc.nextInt();
            int k = sc.nextInt();

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

        int[] accDelta = new int[N + 1];

        for (int i = 1; i <= N; i++)
            accDelta[i] = accDelta[i - 1] + delta[i];

        for (int i = 1; i <= N; i++)
            System.out.print(origin[i] + accDelta[i] + " ");

        System.out.println();
    }
}

---

강의 코드

코드

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] origin = new int[N + 1];

        for (int i = 1; i <= N; i++)
            origin[i] = sc.nextInt();

        int[] delta = new int[N + 2];

        while (M-- > 0) {

            int a = sc.nextInt();
            int b = sc.nextInt();
            int k = sc.nextInt();

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

        int[] accDelta = new int[N + 1];

        for (int i = 1; i <= N; i++)
            accDelta[i] = accDelta[i - 1] + delta[i];

        for (int i = 1; i <= N; i++)
            System.out.print(origin[i] + accDelta[i] + " ");

        System.out.println();
    }
}

---

내 코드 vs 강의 코드 비교

1. 코드 구조

완전히 동일한 코드

→ 풀이 방식 차이 없음

---

2. 핵심 로직

두 코드 모두 동일하게

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

를 사용한다.

---

3. 누적합 처리

accDelta[i] = accDelta[i-1] + delta[i];

→ 구간 영향 적용

---

핵심 차이

없음 (완전히 동일)

---

핵심 개념

1. 차분 배열 (Difference Array)

구간 업데이트를 빠르게 처리하는 기법

---

원리

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

---

의미

a부터 시작해서 +k
b 이후부터 -k

---

2. 누적합

accDelta[i] = accDelta[i-1] + delta[i]

→ 실제 값 복원

---

3. 최종 값

origin[i] + accDelta[i]

---

시간 복잡도

• 명령 처리: O(M)
• 누적합 계산: O(N)

전체

O(N + M)

---

정리

이 문제는 단순 구현 문제가 아니라
구간 업데이트 최적화 문제였다.

핵심은 다음이다.

차분 배열 + 누적합

내 코드와 강의 코드는 완전히 동일하며,
핵심 개념을 정확히 이해하고 구현한 상태이다.

이 문제를 통해 얻을 수 있는 중요한 포인트는 다음과 같다.

1. 구간 업데이트는 직접 하면 안 된다
2. 차분 배열을 사용하면 O(1)로 처리 가능
3. 마지막에 누적합으로 복원

즉,

구간 문제 = 차분 배열 or 누적합

이라는 것을 반드시 기억해야 한다.