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

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

 

 

사용 알고리즘: 누적 합

 

 

입력

• 수의 개수 N ( 1 ≤ N ≤ 100,000 )
• 합을 구해야 하는 횟수 M ( 1 ≤ M ≤ 100,000 )
• N 개의 수
• M 개의 i, j 쌍

 

만약 이 문제를 파이썬 내장함수인 sum 을 사용해서 푼다면 시간초과로 실패한다. 

 

sum 함수의 시간 복잡도는 O(n) 이고 M 개의 i,j 쌍의 구간 합을 구하기 위해 for 문을 M 번 돌면  총 시간 복잡도는 O(MN) 이 된다. 

최대 N 값인 100,000 과 최대 M 값이 100,000 을 곱한 값은 10,000,000,000 로 100 억이 되는데, 컴퓨터가 1초에 계산할 수 있는 횟수는 대략 1억번이다. 문제에서 주어진 제한 시간은 1초이므로 시간 초과로 실패하게 된다. 

 

그래서 누적 합이라는 알고리즘을 사용해야 이 문제를 통과할 수 있다. 

 

- 누적합 알고리즘

[Aligorithm/알고리즘] 누적합 알고리즘 Prefix Sum

 

 

s 라는 누적 합을 저장할 배열을 만들고 초기화

(입력에서 주어진 i, j 쌍은 인덱스 기반이 아니라 인덱스 0번을 첫번째 숫자로 생각하기 때문에 편하게 계산하기 위해 배열을 N+1 길이로 초기화 시킴, 1번 인덱스부터 사용하기 위함)

 

for 문을 돌면서 처음 인덱스 ~ j 번째 인덱스까지의 부분합을 구해 누적 합 배열에 저장한다. 

s = [0] * (N+1)
s[1] = arr[0]

for j in range(2, N+1):
    s[j] += s[j-1] + arr[j-1]

 

 

미리 계산해둔 누적 합 s 배열을 이용해 계산

 

ex)

1~3번째 숫자의 부분 합 구하기 -> s[3] - s[0]

for i in range(M):
    start, end = map(int, input().split(' '))
    print(s[end] - s[start-1])

 

 

 

전체코드

import sys
input = sys.stdin.readline

# 입력받기
N, M = map(int, input().split())
arr = list(map(int, input().split()))

# 누적합 배열 초기화
s = [0] * (N+1)
s[1] = arr[0]

# 처음~i 번째 인덱스까지의 각 부분합 구하기
for j in range(2, N+1):
    s[j] += s[j-1] + arr[j-1]

# 위에서 구한 부분합을 사용해서 주어진 구간의 부분합 구하기
for i in range(M):
    start, end = map(int, input().split(' '))
    print(s[end] - s[start-1])