백준 11659번. 구간 합 구하기 4 (Python / 파이썬)

문제

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

입력

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

출력

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

---

문제 풀이 

N개의 수가 주어졌을 때 i번째부터 j번째 수까지의 합을 구하는 문제이다.

이 문제를 반복문을 사용해서 해결하면 시간초과 문제가 발생한다. 

따라서, 앞에서부터 차례로 합한 결과를 먼저 배열에 넣어준 뒤 

j번째 까지 합한 결과와 i-1 번째까지 합한 결과를 빼주어 답을 구해주었다. 

 

예를 들어, 5 4 3 2 1 에서 1번째부터 3번째 수까지의 합을 구한다고 하면 

첫 번째 수까지 더한 결과, 두 번째 수까지 더한 결과를 차례대로 배열에 저장해준다. 

결과는 아래 표와 같다. 

5

9

12

14

15

1번째부터 3번째 수까지의 합을 구하려면 3번째 수까지 더한 합에서 0번째 수까지 더한 합을 빼야 한다. 

따라서 답은 12 - 0 = 12가 된다. 

이러한 과정을 동일하게 적용하면 답을 시간초과 문제 없이 구할 수 있다. 

---

My Code

import sys 
input = sys.stdin.readline 

n, m = map(int, input().split()) # 수의 개수, 구할 횟수

array = list(map(int,input().split())) # n개의 수

sum_value = 0 
res = [0] 
for i in array:
    sum_value += i # 앞에서부터 합을 구해
    res.append(sum_value) # 배열에 저장

for _ in range(m):
    a, b = map(int,input().split()) 
    print(res[b] - res[a - 1]) # a번째부터 b번째 수까지의 합을 구함