[BOJ / PYTHON] 11659. 구간 합 구하기 4

정답코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
nums = list(map(int, input().split()))
prefix_sum = []
for i in range(N):
    if i == 0:
        prefix_sum.append(nums[i])
    else:
        prefix_sum.append(prefix_sum[i - 1] + nums[i])

course = []
for _ in range(M):
    i, j = map(int, input().split())
    if i == j:
        if i != 1:
            print(prefix_sum[j - 1] - prefix_sum[i - 2])
        else:
            print(prefix_sum[i - 1])

    elif i != 1:
        print(prefix_sum[j - 1] - prefix_sum[i - 2])

    else:
        print(prefix_sum[j - 1])

전략

시간 초과를 해결하기 위해서 누적 합이라는 개념을 도입한다.
누적 합 배열은 원본 배열을 차례로 누적해 저장하는 배열이다.

출력 값은 입력 받은 구간 i, j 사이의 값들의 합이다.
이 말은 j 번째 까지의 누적 합에서 i 번째의 누적 합을 빼면 나오는 값이다.
구간의 예외 처리를 유의하여 문제를 해결한다.

!!input() 으로 입력받지 말고, sys.stdin.readline 으로 반드시 입력 받는다!!