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

문제 바로가기

풀이

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000

리스트의 길이(N)가 최대 100,000 , 구간합 구하는 명령(M)이 최대 100,000 이므로 완전 탐색을 이용하면 시간초과가 발생하기 때문에 미리 누적합을 구해 [i,j] 구간에 있는 리스트의 값을 더하여 문제를 해결한다.

• 리스트 슬라이드 사용 시 시간초과 발생

import sys

N, M = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
i = 0

while i < M:
    start, end = map(int, sys.stdin.readline().split())
    print(sum(num[:end]) - sum(num[:start-1]))
    i += 1

• accumulate 함수를 이용하여 구간합 리스트를 미리 생성하여 구간 합을 계산

import sys
from itertools import accumulate

N, M = map(int, sys.stdin.readline().split())

num = list(map(int, sys.stdin.readline().split()))
num = list(accumulate(num))
num.append(0)

i = 0
while i < M:
    start, end = map(int, sys.stdin.readline().split())
    print(num[end - 1] - num[start - 2])
    i += 1

• 구간합 리스트 생성방법 2

n = int(input())
num = list(map(int, input().split()))
num_acc = [0]
i = 0
while i < n:
    num_acc.append(num_acc[-1] + num[i])
    i += 1