[Python]백준 11441/합 구하기 / 누적합

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

11441번: 합 구하기

 

⚡️ 문제 설명

총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램

⚡️ 해결 방법

처음에

for _ in range(m):
    i,j=map(int,input().split())
    print(sum(A[i-1:j]))

이렇게 코드를 작성하여 더하였더니 시간초과가 발생하였다. 

시간초과를 해결하기 위해서는 누적합을 구해야한다.

 

#누적합

B=[0]*(n+1)
for i in range(1,n+1):
    B[i]=B[i-1]+A[i-1]

A=[10,20,30,40,50]일 때에

누적합 리스트 B=[0,10,30,60,100,150] 이다.

 

i,j가 1,3일 때는

B[3]-B[0]을 구하면 정답이 된다. 

 

⚡️ 코드

import sys
input = sys.stdin.readline

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

#누적합
B=[0]*(n+1)
for i in range(1,n+1):
    B[i]=B[i-1]+A[i-1]


for _ in range(m):
    i,j=map(int,input().split())
    print(B[j]-B[i-1])