[백준 11659] 구간 합 구하기 4 (실버 3) Python

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

11659번: 구간 합 구하기 4

---

문제

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

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

접근 방법

가장 먼저 떠오르는 해결책은 단순히 리스트에서 i~j 부분을 슬라이싱 한 뒤 합을 구하는 방법이다. 하지만 해당 방법은 시간 복잡도가 O(n*m)가 소요되어, 최대 100000 **2 번의 연산이 수행될 수 있어서 시간초과가 발생한다.

이에 각 구간의 합을 메모리에 저장하고, 필요한 부분을 꺼내 쓰는 Dynamic programming 방식을 활용하여 문제를 해결하였다.

# 백준 11659 구간 합 구하기 4 https://www.acmicpc.net/problem/11659
# n개의 수에서 i~j번째 수의 합을 구하라.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nums = list(map(int, input().split()))

summation = 0
summation_list = [0]
for k in range(n):
    summation += nums[k]
    summation_list.append(summation)

for _ in range(m):
    i, j = map(int, input().split())
    # print(sum(nums[i-1:j])) # 시간초과 발생
    print(summation_list[j] - summation_list[i-1])

먼저 순차적으로 합을 저장할 summation 변수와, 각 시점별 summation을 저장할 summation_list를 선언해준다. 이때 summation_list의 첫 번째 인덱스는 0으로 해준다. 이렇게 해야 i~j 구간합을 구할 때 정확한 값을 불러올 수 있다.

먼저 0부터 n-1까지 for문을 돌면서  summation과 summation_list를 만든다. 이렇게 해주면 summation_list의 각 인덱스에는 0부터 해당 인덱스까지의 누적합이 저장된다. 예제 1번의 경우 summation_list에는 [0, 5, 9, 12, 14, 15]가 저장된다.

 

그 뒤, m만큼 반복문을 돌면서, i부터 j까지의 구간합을 계산해서 출력해준다. 이때 summation_list[j]는 nums[0]부터 nums[j-1]까지의 값이 저장되어 있다. 이 summation_list[j]에서 summation_list[i-1] 값을 빼주게 되면, i~j까지의 구간합을 구할 수 있다. 

예를 들어,

i=1, j=3이라면 summation_list[j] - sjmmation_list[i-1] = 12 - 0 = 12가 되고,

i=2, j=4라면 summation_list[j] - sjmmation_list[i-1] = 14 - 5 = 9 가 된다.

 

이렇게 DP를 이용해 계산하게 되면 연산량은 0~n-1 까지의 for문 연산량 n, m까지의 for문 연산량 m, summation_list에서의 인덱싱 연산량 n 을 합해서 2n+m만큼의 연산만으로 문제를 해결할 수 있다.