09009

[백준 11659번] 구간 합 구하기 4 본문

Algorithm/누적합
[백준 11659번] 구간 합 구하기 4
09009

문제 보기

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

 

11659번: 구간 합 구하기 4

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

www.acmicpc.net

 

 

소스 코드

import sys
input = sys.stdin.readline

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

sum_arr = [0] * (n+1)

tmp_sum = 0
for i in range(len(arr)):
    tmp_sum += arr[i]
    sum_arr[i+1] = tmp_sum

for _ in range(m):
    x,y = map(int,input().split())
    print(sum_arr[y] - sum_arr[x-1])

 

문제 해결

누적 합 리스트를 편의 상 원래의 리스트 (arr) 길이보다 하나 길게 생성하고 0으로 초기화하여 해결한다.

 

 

'Algorithm > 누적합' 카테고리의 다른 글

[백준 2559번] 수열  (0) 2023.10.19
'Algorithm/누적합' Related Articles more
Comments