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

---

문제 분석

문제에서 수의 개수와, 합을 구해야 하는 횟수는 최대 100,000이다. 게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다. 따라서 구간합을 이용하여 문제를 풀도록 한다.

---

'구간합'이란?

배열 A의 합 배열을 S라고 할때,
S[i] = A[0] + A[1] + A[2] + ... +A[i-1]+A[i] 로 표현 가능

---

합 배열 S를 만드는 공식
-> S[i] = S[i-1]+A[i]

---

구간합을 구하는 공식 (i번째 인덱스에서 j번째 인덱스 구간의 합을 구한다고 할때)
-> S[j] - S[i-1]

소스 코드

# 구간 합 구하기4

import sys
input = sys.stdin.readline

N, M = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
arrSum = [0]*(N+1)

for i in range(1, N + 1):
    arrSum[i] = arrSum[i-1] + arr[i - 1]

for _ in range(M):
    start, end = map(int, input().split(' '))
    print(arrSum[end] - arrSum[start - 1])

여러 줄을 입력받는 경우 시간초과 문제 발생하기에 아래와 같이 처리해주어 해결하도록 한다.
import sys
input = sys.stdin.readline