백준 11659번 : 구간 합 구하기 4 in Python

11659번: 구간 합 구하기 4

 

www.acmicpc.net

이 문제는 수 N개가 주어졌을 때 i번째 수부터 j번째 수까지 합을 구하는 문제이다.

만약 주어지는 (i, j) 쌍의 수가 적다면 단순히 i번째 수부터 j번째 수까지 더하면 끝나지만, 문제는 주어지는 (i, j) 쌍의 수가 최대 10^6개까지 가능하다는 점이다. 그러므로 매번 (i, j) 쌍이 주어질 때마다 합을 직접 구하려고 하면 O(NM)의 시간이 소요돼 비효율적인 알고리즘이 된다. 그러므로 좀더 효율적인 알고리즘을 고안할 필요가 있다.

이를 해결하는 효율적인 알고리즘 중 하나는 수열의 합에서 아이디어를 착안할 수 있다. 어떤 수열의 일반항 a_n이 주어진 경우 이를 이용해 수열의 합의 일반항 S_n을 구할 수 있다. 여기서 S_n은 a_k를 k=1부터 k=n까지 더한 결과를 의미한다. 이때 만약 k=i부터 k=j까지 a_k를 더한 결과를 알고 싶다면 직접 a_k를 더하는 방법도 있지만 S_j에서 S_i-1을 빼서 구할 수도 있다. 즉, 만약 수열의 합의 일반항을 구할 수 있으면 이를 이용해 k=i부터 k=j까지 a_k를 더한 결과를 constant time 안에 계산할 수 있다.

이 아이디어를 바탕으로 i번쨰 인덱스에 해당하는 entry에 첫 번째 원소부터 i번째 원소까지 더한 결과를 저장하는 배열을 만든 뒤 (i, j) 쌍이 주어질 때마다 배열의 j번째 entry에서 (i-1)번째 entry를 뺀 결과를 출력한다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
nums = [0] + list(map(int, input().split()))
# 배열의 각 entry가 첫 번째 원소부터 시작한 구간의 합을 저장하도록 한다.
for i in range(1, N+1):
    nums[i] += nums[i-1]
for _ in range(M):
    i, j = map(int, input().split())
    print(nums[j] - nums[i-1])