[🥈3 / 백준 11441 / 파이썬] 합 구하기

 

 

 

11441번: 합 구하기

 

 

문제

N개의 수 A₁, A₂, ..., A_N이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A₁, A₂, ..., AN이 주어진다. (-1,000 ≤ A_i ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

 

출력

총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

 

 

예제 입력 1 5 10 20 30 40 50 5 1 3 2 4 3 5 1 5 4 4	예제 출력 1 60 90 120 150 40
예제 입력 2 3 1 0 -1 6 1 1 2 2 3 3 1 2 2 3 1 3	예제 출력 2 1 0 -1 1 -1 0

 

 

풀이

 

누적 합으로 주어진 구간의 합을 빠르게 구하는 문제이다.

주어진 1차원 리스트 A를 왼쪽부터 차례로 더해 인덱스 0부터 현재까지의 합을 담도록 바꾼다.

이후, 범위 i, j 가 주어지면 A[j] - A[i] 를 하면 구간의 합을 구할 수 있다.

 

import sys
input = sys.stdin.readline

n = int(input())
lst = [0]
for i in map(int,input().split()):
    lst.append(lst[-1] + i)
for _ in range(int(input())):
    a, b = map(int,input().split())
    print(lst[b] - lst[a-1])