🥚문제링크

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

• 누적 합

---

🍳코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [0] + list(map(int, input().split()))
prefix_sum = [0]*(N+1)

# prefix_sum[i] = 1번째 숫자부터 i번째 숫자까지의 합을 저장
for i in range(1, N+1):
    prefix_sum[i] = prefix_sum[i-1] + nums[i]

for _ in range(M):
    # i번째 수부터 j번째 수까지의 합
    # = prefix_sum[j] - prefix_sum[i-1]
    i, j = map(int, input().split())
    print(prefix_sum[j] - prefix_sum[i-1])

---

🧂아이디어

누적 합

1. prefix_sum[i]에 1번째 숫자부터 i번째 숫자까지의 합을 저장한다.

2. i번째 수부터 j번째 수까지의 합을 구하려면 prefix_sum[j] -prefix_sum[i-1]을 한다.

   • 예를 들어, 숫자가 5, 4, 3, 2, 1로 주어졌을 때
     prefix_sum = [0, 5, 9, 12, 14, 15]
     여기에서 2~4의 구간 합 = prefix_sum[4] - prefix_sum[1] = 9

   • prefix_sum[4] = 5 + 4 + 3 + 2
prefix_sum[1] = 5
     이기 때문에 2~4의 구간 합인 4 + 3 + 2를 올바르게 구해낼 수 있다.

   • 위와 같은 방식으로 구간 합을 구하면
     i에서 j까지 for문을 이용해서 더하는 것(문제에서 i ~ j의 합을 구하는 최악은 100,000번 연산)보다 빠르게(prefix_sum[j] -prefix_sum[i-1] 연산 단 한 번, O(1)에 끝) 결과를 도출할 수 있다.

참고: https://www.crocus.co.kr/843