백준 11659 — 구간 합 구하기 4: 누적합의 차이 이용하기

문제

백준 11659 구간 합 구하기 4 문제 화면

1. 테이블 정의하기

D[i] = 첫 번째 숫자부터 i번째 숫자까지의 누적합

numbers = [5, 4, 3, 2, 1]
 
D[0] = 0
D[1] = 5
D[2] = 9
D[3] = 12
D[4] = 14
D[5] = 15

여기서 D[0] = 0을 하나 추가해두면 인덱스 계산과 예외 처리가 단순해진다.

2. 점화식 찾기

D[i] = D[i - 1] + numbers[i - 1]; // numbers는 0부터 시작

1 ~ i까지의 합
=
1 ~ (i - 1)까지의 합
+
i번째 숫자

이를 활용해서 i부터 j까지의 합은 다음처럼 나타낼 수 있다.

sum(i, j) = D[j] - D[i - 1]

1부터 j까지의 합에서 1부터 i-1까지의 합을 빼면 원하는 구간만 남는다. i가 1이어도 D[0] = 0 덕분에 같은 공식을 쓸 수 있다.

3. 초기값 정의하기

DP[0] = 0;

4. 코드 구현하기

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
 
const [firstLine, n, ...inputs] = fs.readFileSync(filePath, 'utf-8').trim().split('\n');
 
const [N, T] = firstLine.split(' ').map(Number);
const numbers = n.split(' ').map(Number);
 
function solution() {
    // D[i] = 1번째 숫자부터 i번째 숫자까지의 누적합
    const D = Array(N + 1).fill(0);
    const results = [];
 
    // 누적합 배열 생성
    for (let i = 1; i <= N; i++) {
        D[i] = D[i - 1] + numbers[i - 1];
    }
 
    // 각 구간의 합 계산
    for (let t = 0; t < T; t++) {
        const [i, j] = inputs[t].split(' ').map(Number);
 
        results.push(D[j] - D[i - 1]);
    }
 
    console.log(results.join('\n'));
}
 
solution();

Prefix Sum(누적합): 배열의 앞에서부터 누적한 합을 미리 저장해두고, 두 누적합의 차를 이용해 임의 구간의 합을 O(1)에 구하는 기법.

DP와 구분해서 기억하기

누적합도 앞서 계산한 결과를 재사용하지만, 이 글의 핵심은 구간 합 질의를 빠르게 처리하는 전처리 기법이다. DP 개념·문제 풀이와 연결해 읽되 누적합이라는 별도 주제로 기억해두자.

복잡도

전처리 O(N), 질의 하나당 O(1), 질의 M개를 포함한 전체 시간 O(N + M). 누적합 테이블은 O(N), 출력 결과를 모으는 배열까지 포함하면 O(N + M) 공간이다.

참고 자료

바킹독의 실전 알고리즘 0x10강 — 다이나믹 프로그래밍을 학습하며 작성한 메모를 바탕으로 정리했다. 포함된 이미지는 원본 학습 메모의 캡처다.