백준 11659 - 구간 합 구하기4 / 구간 합(Prefix Sum) 알고리즘

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

문제

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

 

 

첫 번째 도전

- 가장 기본적으로 파이썬의 리스트 슬라이싱을 이용하여 풀이하였다.

예를들어 3번째부터 6번째까지의 합을 구하라고하면

result = sum(nums[3-1 : 6]) 로 구하면 된다.

 

하지만 이 문제는 케이스수가 최대 10만, 각 케이스별로 최대 배열 10만 이라서

이렇게 풀면 시간초과다.

 

두 번째 도전 - 구간 합 (Prefix Sum) 알고리즘

예를들어 

nums = [3, 5, 2, 7, 9, 8, 1, 6, 4]

란 배열 이있다고 하자.

이 때, i번째 인덱스에는 i번째 합한 수를 저장한 배열 sums를 정의하자.

n = 9
nums = [3, 5, 2, 7, 9, 8, 1, 6, 4]
sums = [ 0 for _ in range(n) ]
for i in range(n):
    if i == 0:
        sums[i] = nums[i]
    else:
        sums[i] = sums[i-1] + nums[i]

 

이렇게 정의한 sums 로 nums 배열의 3번째부터 6번째 까지의 합을 빠르게 구할 수 있다.

result = sums[6-1] - sums[3-2] 

 

전체 코드

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
nums = list(map(int,input().split()))
sums = [0 for _ in range(n)]
sums[0] = nums[0]
for i in range(1,n):
   sums[i] = sums[i-1] + nums[i]

for _ in range(m):
    i, j = map(int, input().split())
    if i == 1:
        print(sums[j-1])
    else:
        print(sums[j-1] - sums[i-2])