[BOJ] 11659 : 구간 합 구하기 4 [누적 합](Python)

문제 링크

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

11659번: 구간 합 구하기 4

소스 코드

import sys
input = sys.stdin.readline

n,m = map(int,input().rstrip().split())
nums = list(map(int,input().rstrip().split()))

for i in range(1,n): # 누적 합 구하기
    nums[i] = nums[i-1] + nums[i]
nums.insert(0,0) # 맨 앞에 0 추가

for i in range(m):
    start,end = map(int,input().rstrip().split())
    print(nums[end] - nums[start-1]) # end - (start-1)

 

해설

• 구간 합 구하기 알고리즘의 대표 유형
• 접두사 합

 

구간 합 알고리즘의 필요성

구간 합 구하기 알고리즘의 대표적인 유형이라고 볼 수 있다.

이 알고리즘을 모른다면 일반적으로 리스트를 슬라이싱하여 구간의 합을 매번 계산하게 될 것이다.

사실 그렇게 접근 하는 것 자체는 문제가 없지만 시간 초과 판정을 피하기 어렵다.

 

특히 n과 m의 범위가 최대 100,000인데 최대 10만번을 10만 길이의 리스트에 대해 슬라이싱을 하고 합을 구하게 되면 시간 복잡도가 지나치게 높아 정답 판정을 받을 수 없다.

 

 

접두사 합 

따라서 현재 인덱스까지의 합을 저장해놓는 접두사 합 방식을 이용해야 한다.

 

주어진 리스트를 순회하며 이전까지 누적된 값에 현재 값을 더하여 저장하는 과정을 반복한다.

리스트의 길이는 최대 100,000이고 시간 복잡도는 o(N)이 될 것이다.

 

주의할 점은 시작점이 자기 자신을 포함하고 있기 때문에 맨 앞에 0을 삽입해주는 것이다.

예를 들어 위 소스 코드에서 start = 1, end = 3 인 경우 5, 4, 3 을 더해야 하는데, 우리가 구간 합을 구할 때는 end - (start-1) 를 계산하므로 인덱스에 에러가 생길 수 있다.

따라서 start = 1 인 경우 아무것도 선택하지 않았다는 것을 의미할 수 있도록 맨 앞에 0을 삽입해준다.

 

이후 다시 한 번 for문으로 m번 입력을 받으며 시작 인덱스와 끝 인덱스를 저장한다.

이전에 입력 받은 리스트는 n + 1의 길이를 가지므로 여기서 입력 받은 시작 인덱스와 끝 인덱스는 그대로 사용 가능하다.

 

단, 시작값은 -1 을 해야 한다.

예를 들어 시작 = 2, 끝 = 4인 경우 2,3,4 번째 숫자를 합한 값을 구하는 것은 (4까지의 누적 합 - 1까지의 누적합) 으로 계산 된다. 

 

즉 시작 전까지의 누적합을 빼줘야 하므로 맨 앞에 0을 추가해준 것이고, 시작 인덱스는 -1을 해줘야 하는 것이다.