[BOJ] 11659 - 구간 합 구하기4

문제 링크

BOJ 11659 - 구간 합 구하기4

문제 설명

첫 줄에는 N개의 숫자와 합을 구해야 하는 횟수 M이 주어진다.
둘째 줄에는 N개의 수가 주어진다. (각각 1000 이하의 자연수)
셋째 줄부터 M개의 줄에는 합을 구해야하는 구간 i, j가 주어진다.

총 M개의 줄에 i번째 수부터 j번째 수의 합을 출력하시오.

제한 조건

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

문제 풀이

처음에는 간단한 문제인 줄 알고 단순 합으로 접근했으나 시간 초과 Fail...

어떻게 하면 구간을 쉽게 구할 수 있을지 생각하던 중 고등학교 때 배웠던 시그마(∑)가 떠올랐다.

원리는 간단하다.

고등학교 수학에서 주어진 n개의 원소를 더할 때 아래와 같이 표현했을 것이다.

우리가 구하고 싶은 것은 i번째 수에서 j번째 수의 합이다.

문제의 입력 케이스인 i=2, j=4 를 예시로 들면 아래와 같은 원소의 합이다.

방법은 간단하다. 4번째 원소까지의 합에서 2번째 원소 직전인 첫번째 원소까지의 합을 빼면 된다.

매번 for문을 돌며 구간의 합을 더하기에는 N, M의 범위가 크기에 크기 N+1의 배열을 선언해서 각 인덱스에는 첫번째 원소부터 해당 인덱스의 원소까지의 합을 저장하도록 하였다.

import sys

N, M = map(int, sys.stdin.readline().split())


arr = [0]*(N+1)
line = list(map(int, sys.stdin.readline().split()))
arr[1] = line[0]

for i in range(2,N+1):
    arr[i] = line[i-1]+arr[i-1] #이전 수를 더하기

for i in range(0,M):
    fNum, sNum = map(int, sys.stdin.readline().split())

    print(f"{arr[sNum]-arr[fNum-1] }")