[python][백준/BOJ] 11659번 : 구간 합 구하기 4 - 누적합, 부분합

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

 

✅ 시간초과 난 코드

import sys

n,m =map(int,sys.stdin.readline().split())
l=list(map(int,sys.stdin.readline().split()))
print(l)
for k in range(m):
    i,j =map(int,sys.stdin.readline().split())
    sum =0
    for q in range(i-1,j):
        sum+=l[q]
    print(sum)

• N,M의 범위가 최대 100,000 이고, i,j 범위를 최대로 했을 경우, 시간복잡도의 최대는 O(N^2) 이기에 시간초과남

 

✅ 누적합(Prefix Sum)

• 배열에서 특정 구간의 합을 빠르게 구할 수 있음
• 단순 이중 for문보다 빠른 O(N) 또는 O(1)의 시간복잡도를 가지며 부분합을 구할 수 있음

arr = [1, 3, 5, 7, 9]  # 예제 배열
# 0부터 시작하는 누적합 배열 생성
prefix_sum = [0] * (len(arr) + 1)  

for i in range(1, len(arr) + 1):
    # 이전 값 + 현재 값
    prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]  

print(prefix_sum)  # [0, 1, 4, 9, 16, 25]

 

✅ 부분합 

• 특정 구간의 [i,j]의 부분합을 O(1)로 구하기
• 부분합 = prefix_sum[j] - prefix_sum[i-1]

arr = [1, 3, 5, 7, 9]  # 예제 배열
# 0부터 시작하는 누적합 배열 생성
prefix_sum = [0] * (len(arr) + 1)

#누적합
for i in range(1, len(arr) + 1):
    # 이전 값 + 현재 값
    prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]

#부분합
i,j=2,4
result =prefix_sum[j]-prefix_sum[i-1]
# 15(3+5+7)
print(result)

 

✅ 최종 수정한 코드

import sys

n,m =map(int,sys.stdin.readline().split())
l=list(map(int,sys.stdin.readline().split()))

#누적합
sum =[0]*(n+1)
for k in range(1,n+1):
    sum[k]=sum[k-1]+l[k-1]

for k in range(m):
    i,j =map(int,sys.stdin.readline().split())
    result=sum[j]-sum[i-1]
    print(result)