[백준] 11659 - 구간 합 구하기 4 (Python)

문제 설명

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

11659번: 구간 합 구하기 4

 

---

문제 풀이

처음에는 i랑 j를 입력받고, 입력 받자마자 i부터 j까지의 합을 구해서 출력하는 방식으로 풀었다

제출했더니 바로 뜨는 시간초과...

최대 N개의 합을 최대 M번 반복해서 하다보니 시간 복잡도는 O(NM)이 된다. 최대 100억

 

입력 받고 합을 구하는 게 아니라 일단 합을 다 구해놓고 구간이 입력되면 바로 출력하는 방법으로 생각해보았다

이 방식으로 접근하다 보니 i부터 j까지의 합을 어떻게 구할지 생각해봤는데

예를 들어 3번째부터 5번째까지의 합이면 

1번째부터 5번째까지의 합에서 1번째부터 2번째까지의 합을 빼주면 3부터 5 구간의 합이 나온다

 

 

import sys

n, m = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
d = [0] * (n + 1)
d[0] = 0

for i in range(1, n + 1):
    d[i] = d[i - 1] + num[i - 1]

for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    print(d[y] - d[x - 1])