[백준] 11659 구간 합 구하기 4 (파이썬 python)

 

 

문제 링크

 

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

11659번: 구간 합 구하기 4

 

 

 

문제 풀이

 

N, M이 각각 10만까지로 만약 범위를 입력받을 때마다 해당 구간에 대해 더하는 연산을 통해 답을 도출한다면

O(NM)의 시간복잡도로 시간초과가 나게됩니다.

매번 합을 도출하는 것이 아니라, 처음에 입력받은 리스트에 대해 누적합을 미리 저장해놓은 후,

만약 i부터 j 인덱스까지의 범위를 구하고 싶을 경우 [ j까지의 누적합 - (i - 1)까지의 누적합 ]의 연산을 통해 구해주면 됩니다.

 

전체 코드

 

import sys
input = sys.stdin.readline

n, m  = map(int, input().split())
nums = list(map(int, input().split()))
for i in range(1, n):
    nums[i] += nums[i - 1]
nums = [0] + nums
for _ in range(m):
    i, j = map(int, input().split())
    print(nums[j] - nums[i - 1])