[Python] 백준 11659번 - 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

혼자 힘으로 풀었는가? : X

알고리즘 유형
 - 누적 합

문제

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

처음에는 단순하게 반복문으로 무한 더하기 했으나 역시나 시간 초과가 발생했고

알고리즘 분류를 보았더니 '누적 합' 이라는 처음 보는 알고리즘 형태를 보게 되어 검색하였더니 생각보다 쉬운 방법이었다.

예시를 기준으로

 

입력번호	1	2	3	4	5
index	0	1	2	3	4
data[]	5	4	3	2	1
누적	5	9	12	14	15

위의 표처럼 모든 합을 더하면서 배열을 만들어 주는 것이다.

 

이것으로 구간합을 구할 수 있다.

 

예시의 '2 4' 구간 합을 얻고자 할 경우

 

1 ~ 4 까지 합 - 1 ~ 1 까지 합 을 빼줘야 2 ~ 4 구간 합을 얻을 수 있다.

 

실제로 4 + 3 + 2 = 9

14 - 5 = 9 인 것을 알 수 있다.

 

즉 식은

 

print(data[j] - data[i-1])

위의 코드와 같다.

 

하지만 위의 코드로 그대로 실행시킬 경우 틀린 코드이다.

 

i = 1 인 경우에는 빼는 값이 없이 누적 합 그대로 출력되어야 하지만 위의 식대로 하면 data[0] 의 값을 항시 빼기 때문에

 

예외 처리를 해주어야 한다.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = list(map(int, input().split()))
sum = 0
for i in range(n):
    sum += data[i]
    data[i] = sum
for _ in range(m):
    i, j = map(int, input().split())
    if i == 1:
        print(data[j-1])
    else:
        print(data[j-1] - data[i-2])