[누적합/백준] 11659번 : 구간 합 구하기 4

- 문제 :https://www.acmicpc.net/problem/11659

 

 

Silver Lv3 문제다!

누적 합은 처음 보는 문제인데, 풀이 논리를 알아둬야할 것 같아서 포스팅한다. 

정수로 이루어진 배열에서 일정 구간의 합을 구할 때 파이썬의 경우 인덱싱으로 바로 구해도 되겠지만 각 M개의 케이스에 대해서 전체 배열을 매번 탐색해야하므로 O(M * N)의 시간복잡도가 된다.

문제의 경우 N, M 모두 최대 10만이므로 최악의 경우 시간 복잡도는 100초(100억개 탐색)가 걸릴 수 있다. 그래서 시간 복잡도를 줄이는 방향으로 로직을 설정해야하는데, 이 때 fast_sum이라는 배열을 이용한다. 

 

fast_sum[i]는 nums[1] ~ nums[i]까지의 누적합을 나타낸다. 따라서 [a, b] 구간의 합을 구하려면 

fast_sum[b](인덱스 1부터 b까지의 합) - fast_sum[a - 1](인덱스 1부터 a - 1까지의 합)을 계산하면된다. 

위 연산으로 수행하면 O(1)의 시간복잡도를 가져서 O(N)보다 훨씬 빠른 속도로 진행할 수 있다.

총 M개의 케이스이므로 전체 시간 복잡도는 O(M)

 

먼저 문제 정보를 저장한 다음에 fast_sum을 계산한 뒤 각 M개의 케이스에 대해서 누적합의 차이를 프린트 해주면 정답이다. 

 

- 정답 풀이 : 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = [0] + list(map(int, input().split()))

fast_sum = [0] * (n + 1) 
fast_sum[1] = nums[1]
for i in range(1, n + 1):
    fast_sum[i] = nums[i] + fast_sum[i - 1]

answer = [] 
for _ in range(m):
    a, b = map(int, input().split())
    answer.append(fast_sum[b] - fast_sum[a - 1])
    
for i in range(len(answer)):
    print(answer[i])

 

관련 내용은 이 블로그에 잘 설명 되어 있다.