[Python] BOJ/백준 11659번 구간 합 구하기 4

[문제]

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

11659번: 구간 합 구하기 4

 

[풀이]

누적 합

누적 합은 구간의 누적 합을 구하는 문제이다.

일반적으로 리스트에 값을 저장하고, 인덱스로 한개씩 더하는 방식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클 때는 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(n)의 시간복잡도로 해결할 수 있다.

누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 쓰일 수 있다.

예를들어 크기가 3인 nums 리스트에서 1번에서 3번 index 구간의 합을 구한다고 하면, 누적합은 nums[0~3까지의 누적 합] - num[0~(1-1)까지의 누적 합]으로 표현할 수 있다.

-> 따라서 B - A 구간의 누적합을 구하기 위해서는 (B 구간까지의 합) - (A - 1 구간까지의 합)을 구하면 된다.

---

누적 합 리스트인 nums_add를 구해놓은 후 start에서 end까지의 합은 nums_add[end] - nums_add[start-1]과 같다.

(nums_add[end]는 end까지 숫자 합, nums_add[start-1]은 start-1까지 숫자 합)

 

[코드]

import sys

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    nums_add = [0]

    for i in range(n):
        nums_add.append(nums_add[-1]+nums[i])
        
    for _ in range(m):
        start, end = map(int, sys.stdin.readline().split())
        if i == 1:
            print(nums_add[end])
        else:
            print(nums_add[end] - nums_add[start - 1])