백준(baekjoon) 11659번: 구간 합 구하기 4(실버 3, 파이썬 PYTHON) - 누적 합

문제

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

 

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

11659번: 구간 합 구하기 4

 

import sys

N,M=map(int,sys.stdin.readline().split())
num_list=list(map(int,sys.stdin.readline().split()))
sum=[]
sum.append(0)

for x in range(1,N+1):
  sum.append(sum[x-1]+num_list[x-1])

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

 

※ 누적 합

 

 

● 수의 개수 N과 합을 구해야 하는 횟수 M을 저장한다. 그 후 입력되는 N개의 수를 num_list배열에 넣어주고, 빈 sum 배열을 정의해준 뒤 sum에 0을 append 해준다. sum[x]에는(x>=1) num_list[x-1] 까지 수의 합이 저장된다.

 

● x는 1부터 N까지 돈다. 각 단계에서는 현재 보고있는 num_list의 숫자와 이 숫자 전까지의 누적합을 더한 값을 차례대로 sum에 append 해준다. 그럼 이 단계에선 현재 보고있는 num_list 숫자 까지의 누적합이 sum에 append 된 것이다. (sum.append(sum[x-1]+num_list[x-1]))

 

● 그 후 합을 구해야 하는 구간 i와 j를 총 M번 입력받는다. 각 i와 j를 입력받은 뒤 이 구간의 합은 sum[j] 에서 sum[i-1]을 빼주면 구간 i부터 j까지의 누적합을 구할 수 있다. sum[j]-sum[i-1] 값을 출력해주면 답을 구할 수 있다.

 

 

결과