백준11659(파이썬) - 구간 합 구하기 4,preifx-sum

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

11659번: 구간 합 구하기 4

• 이 문제는 보기에는 간단해보여서 쉽게 풀었는데 잘 보니까 시간 초과를 유념해서 풀어야 하는 문제 였다.
• 구간 합 문제(prefix-sum) 은 한 가지 알아둬야 하는 개념이 있다. 예를 들어보자. 

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

prefix_sum = [0]
for i in data:
    num += i
    prefix_sum.append(num)

prefix_sum = [1,3,6,10,15,21,28,36,45]

이렇게 prefix_sum 리스트를 만들어줘서 각각 인덱스에 들어있는 숫자를 더해주면 prefix_sum개념을 적용할 리스트를 만든 것이다. 아래와 같이 코드를 작성해서 구간합을 구하면 시간복잡도가 O(1) 이다.

# 구간합 코드
prefix_sum[end] - prefix_sum[start-1]

# 예시) 1부터 4까지의 구간합
int sum = prefix_sum[4] - prefix_sum[0];

 

그래서 11659번 문제의 풀이는 다음과 같다.

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
data = list(map(int,input().split()))

num = 0
prefix_sum = [0]
for i in data:
    num += i
    prefix_sum.append(num)

def function(start,end,prefix_sum):
    return prefix_sum[end] - prefix_sum[start-1]
    

for _ in range(m):
    a,b = map(int,input().split())
    print(function(a,b,prefix_sum))