[BOJ] 구간 합 구하기 4 in Python

문제 풀러 가기!

전형적인 DP 문제로 입력값이 많기 때문에 구간 마다 더하면 안됩니다. 처음 배열을 입력 받을 때 해당 배열의 누적합을 기록해준 다음 이를 이용하여 구간합을 구해주어야 합니다. 0번 index부터 차례로 하나씩 누적시키면 연산 횟수는 최대 10만번이기 때문에 1초 100,000,000을 넘지않으면서 구할 수 있습니다.

즉 i와 j의 구간합은 j번째 누적합 - i-1번째 누적합을 의미하므로
배열에 접근할 때는 시간 복잡도가 O(1)이기 때문에 빠르게 연산이 가능합니다.

이 문제에서는 O(n**2)이 아니라 O(n)으로 문제를 풀어야 한다는 것이죠.
결국 해당 문제를 종합적으로 살펴봤을 때, n 최대 10만개, m 최대 10만개로 20만번의 순회 끝내 모든 답이 도출되게 됩니다.

아래는 제 풀이 코드입니다.

# 입력값이 100,000으로 O(n**2)으로 했을 때 100,000,000이 넘어가므로
# 완전탐색으로 문제를 풀기보다 중복되는 부분을 제거해야한다.

import sys

# readline으로 읽는 경우 input처럼 한 줄 한 줄 입력값을 읽는 것이 아니 한번에 모두 읽어버리는 것이기 때문에
# 더 빠르게 시간을 단축시킬 수 있다.

n, m = map(int, sys.stdin.readline().split())
n_arr = [0]+list(map(int, sys.stdin.readline().split()))

# 1번째 원소부터 누적합 시킨다.
for k in range(1, len(n_arr)):
    n_arr[k] += n_arr[k-1]

# 이후 i와 j를 입력받으면서 각 구간을 합을 출력해준다.
# j번째까지 합 - i번째까지 합을 해주면 된다.
# 이때 누적합을 기록했기 때문에 n_arr를 index 슬라이싱 하므로
# O(1)로 접근이 가능하다.

for l in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(n_arr[j]-n_arr[i-1])