[백준] 구간 합 구하기 4 풀이(파이썬/python/구간 합/prefix sum)

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

예제 입력

 

5 3
5 4 3 2 1
1 3
2 4
5 5

 

예제 출력

12
9
1

 

 

구간 합을 사용한 문제풀이

구간 합(prefix sum) :

주어진 수열에서 임의의 구간에 포함된 요소의 합을 빠르게 구하는 방법

앞에서부터 합을 누적하여 미리 계산해 저장해 놓고 활용하는 방법입니다

 

주어진 리스트 : numbers[0]~numbers[n] 까지 일때

주어진 리스트에서 idex 까지의 합은 numbers[0] 부터 numbers[index] 까지 합을 의미합니다.

리스트의 start부터 end 까지 요소들의 합 더하기는

현재 요소와 이전의 모든 요소들을 합한 리스트인 prefix_sum 리스트를 구해 놓은 뒤

prefix_sum[end] - prefix_sum[start - 1]을 계산할 수 있습니다.

 

이 문제에서도 마찬가지로

현재 요소와 이전의 모든 요소들을 합한 리스트인 prefix_sum 리스트를 만들고

i ~j 구간의 합은 먼저  0 번째 요소부터 j  까지의 합을 구한 뒤 0번째 부터 i까지의 합을 빼면 됩니다.

 

예) numbers =  [ 5, 4, 3, 2, 1]

prefix_sum = [0 , 5, 9, 12, 14, 15] #문제에서 첫번째 요소를 0이 아닌 1번째라고 함으로 0 넣어주기

i = 2, j = 4일 때,  prefix_sum[j]  - prefix_sum[i-1] #2번째 요소 + 3번째 요소 + 4번째 요소 

 

 파이썬 코드

N ,M = map (int, input().split())
numbers = list(map(int, input().split()))
#입력받은 i와 j 리스트로 정리
i_j_list =[]
for m in range(M):
    i_j = list(map(int,input().split()))
    i_j_list.append(i_j)
# prefix_sum 리스트 만들기    
prefix_sum = [0]
numbers_sum = 0
for number in numbers:
    numbers_sum += number
    prefix_sum.append(numbers_sum)
# prefix_sum을 사용해서 주어진 구간의 합 구하기    
for i_j in i_j_list:
    i , j = i_j[0], i_j[1]
    print(prefix_sum[j] - prefix_sum[i-1])

 

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

11659번: 구간 합 구하기 4