🟩 [백준] [Python] Class3_11659번_구간 합 구하기 4

문제

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

11659번: 구간 합 구하기 4

풀이

# 백준 11659번 문제 - 구간 합 구하기
import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, input().split()))

sum_list = [0]
total = 0
for i in range(len(arr)):
    total += arr[i]
    sum_list.append(total)
for _ in range(m):
    i, j = map(int, input().split())
    print(sum_list[j] - sum_list[i-1])

구간합을 살펴보면

# S는 0부터 i까지의 구간합
S = [0,5,9,12,14,15]
# 0~2의 구간합
arr[0] + arr[1] + arr[2] = 12
S[3] - S[0] = 12 - 0 = 12

# 1~3의 구간합
arr[1] + arr[2] + arr[3] = 9
S[4] - S[1] = 14 - 5 = 9

이와 같은 공식을 얻을 수 있다. 

이를 통해 i 부터 j 까지의 구간합은

(j+1까지의 구간합) - (i까지의 구간합) 이라고 볼 수 있다. 

공식을 얻게되면 문제를 쉽게 해결할 수 있다.