[76일차][백준][누적합][11659]구간 합 구하기 4

문제 설명

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

입력

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

 

출력

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

 

제한

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

 

예제 입력, 예제 출력

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

12 9 1

 

코드 및 설명

이 문제는 누적합 문제이다.

처음 입력 받는 수의 개수 N과 합을 구해야하는 횟수 M, 둘째 줄에는 N개의 수가 주어진다. 셋째 줄은 구간 i와 j

N = 5 -> 5가 뜻하는 바는 둘째 줄에 5,4,3,2,1 의 개수이다. 

M = 3 -> 3번 입력을 받는다.

i, j = 구간의 범위를 입력 받는다.

import sys

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

n_sum_arr = [0] * (len(n_arr)+1)

for idx in range(1, len(n_sum_arr)):
  n_sum_arr[idx] = n_sum_arr[idx-1] + n_arr[idx-1]

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

 

일단 n, m을 받는 데 int로 형 변환, 둘째줄에 있는 5,4,3,2,1은 배열로 만들어준다. 누적합은 배열에 1번째 부터 시작하므로, 먼저 배열의 크기를 [0] * (len(n_arr)+1) 지정해주고, n_sum_arr에 누적된 합을 저장해준다. 그 후 m번 입력 받아 i와 j 즉 구간 범위를 받고 출력해준다.