[BOJ] 11659. 구간 합 구하기 4 (Python)

11659번: 구간 합 구하기 4

세그먼트 트리 알고리즘을 공부해야겠다 라고 생각만 하다가 이번 코테에서 제대로 뒷통수 맞고 공부하는 글...

소 잃고 외양간 고치기...^^...껄껄

 

일단 이 문제는 세그먼트 트리로 문제를 풀기에 앞서 DP로 풀어보는 문제이다!

구간 합이란 i번째 숫자부터 j번째 사이의 숫자 합을 구하라는 뜻이다.

 

문제의 예제로 설명해보자면

다음과 같이 숫자가 저장이 되어있을 때

5 | 4 | 3 | 2 | 1 
2 ~ 3 번째 구간 합을 구하세요! 라고 하면 3 + 2 = 5를 구하는 것이다!

 

이를 간단하게 생각하면 i부터 j까지 더하면 되는 것 아닌가? 라고 생각할 수 있다.

물론 배열에서 구간 합을 한 번 구할 때는 그냥 구하는 것이 나을 것이다.

그러나 11659번 문제와 같이 배열이 한 번 주어지고, 그 안에서 구간 합을 여러 번 구해야하는 상황이라면 이야기가 좀 다르다.

 

0 ~ 1번째 구간 합 구하세요 : 5 + 4

0 ~ 2번째 구간 합 구하세요 : 5 + 4 + 3

0 ~ 3번째 구간 합 구하세요 : 5 + 4+ 3 + 2

0 ~ 4번째 구간 합 구하세요 : 5 + 4+ 3 + 2 + 1

...

이런 식으로 이미 구했던 부분을 또 구하고, 또 구하고, 또 구해야 한다는 것..!

따라서 이를 DP로 풀어 한 번 구했던 값들을 또 구하지 않는 것이 이 문제의 핵심이다. 

 

그렇다면 어떻게 구했던 값들은 또 구하지 않을 수 있을까? 

바로 딱 한 번만 전체 누적값을 구해서 저장해두면 된다!

 

0 | 5 | 9(5+4) | 12(9+3) | 14(12+2) | 15(14+1)

 

배열을 딱 한 바퀴를 돌면 전체 누적합을 구할 수가 있다.

그리고 나서 i번째 ~ j번째 부분합을 구하세요 라고 하면

누적합 배열의 j번째 값 - (i-1)번째 값을 해주면 된다는 것!

 

예를 들어 2 ~ 3 번째 구간 합을 구하세요 : 14 - 9 = 5

 

따라서 배열을 한 바퀴만 돌면 계속해서 구간 합을 구할 수 있는 것이다.

그러나 이보다 더 좋은 시간 복잡도로 구하는 방법은 세그먼트 트리를 쓰는 것이다.

이 방법은 다음에 설명하도록 하겠다.

 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = list(map(int, input().split()))
cumsum = [0 for _ in range(n+1)]

for i in range(1, n+1) : # 누적 합 구하기
    cumsum[i] = cumsum[i-1] + array[i-1]

for _ in range(m) :
    i, j = map(int, input().split())
    print(cumsum[j] - cumsum[i-1])