[Python][백준] 누적 합 알고리즘 | 11659번 구간 합 구하기 4 시간초과 해결

누적 합(prefix sum)이란?

 

배열에서 특정 구간의 합을 구할 때 사용하는 방법이다.

만약 이때 일반적인 순회법을 사용하면 시간복잡도가 O(n^2)일 것이다.

하지만 누적 합을 사용하면 O(n)의 시간복잡도를 가진다.

# 리스트를 슬라이싱하고, 합을 구하는 소스코드... 시간초과

import sys


def P11659():
    N, M = map(int, input().split())
    numbers = [0] + list(map(int, input().split()))
    for _ in range(M):
        s, e = map(int, input().split())
        print(sum(numbers[s-1:e]))


if __name__ == '__main__':
    input = sys.stdin.readline
    P11659()

 

 

아래 그림이 일반 배열을 누적합 배열로 바꾼 것이다.

누적 합

이것을 이용하여 배열의 특정 구간의 합을 구할 수 있다.

구간의 합

2~4번째 요소의 합은 4까지의 누적합에서 1까지의 누적합을 뺀것과 같다.

 

 

아래 코드는 누적합을 구현한 것이다.

# print(sum(numbers[s-1:e]))
# 시간초과... 슬라이싱은 느림
# 누적합을 이용하자!

import sys


def P11659():
    N, M = map(int, input().split())
    numbers = [0] + list(map(int, input().split()))
    # 누적합 계산
    for i in range(1, N+1):
        numbers[i] += numbers[i-1]

    for _ in range(M):
        s, e = map(int, input().split())
        print(numbers[e] - numbers[s-1])


if __name__ == '__main__':
    input = sys.stdin.readline
    P11659()