[백준] 11659번 구간 합 구하기 4

💡문제접근

• sum을 사용하면 반복문을 사용하여 i부터 j까지 합을 구하는 과정과 동일한 시간이 발생한다. 따라서 이 문제는 i와 j가 주어질 때마다 i부터 j까지 더하는 방식이 아니라 구간별 누적합을 미리 구해서 값을 가져오는 방식으로 접근하면 시간이 덜 소요된다.

💡테스트케이스 설명

입력

5 3
5 4 3 2 1
1 3
2 4
5 5

출력

12
9
1

• [1:1] 구간 합 : 5
• [1:2] 구간 합 : 9
• [1:3] 구간 합 : 12
• [1:4] 구간 합 : 14
• [1:5] 구간 합 : 15

📌 예를 들어 [2:4] 구간 합을 구하려면 [1:4] 구간 합에서 [1:1] 구간 합을 빼주면 된다. 따라서 답은 14 - 5 = 9가 된다.

💡코드(메모리 : 40584KB, 시간 : 240ms)

import sys

N, M = map(int, sys.stdin.readline().strip().split())
li = list(map(int, sys.stdin.readline().strip().split()))

prefix_sum = [0]
sum_val = 0
for i in li:
    sum_val += i
    prefix_sum.append(sum_val)

for _ in range(M):
    i, j = map(int, sys.stdin.readline().strip().split())
    print(prefix_sum[j] - prefix_sum[i-1])

💡소요시간 : 18m