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

1. 문제

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

2. 풀이

• 배열 크기와 반복횟수를 입력받는다
• 리스트를 입력받는다
• 누적합 방식을 기존 리스트 값과 이전 누적된 값을 더해 추가한다.
• j의 해당하는 누적합 값에서 i에 해당하는 누적합 값을 뺸 후 출력한다.

3. 코드

누적합 방식

import sys

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

for i in range(n):
    prefix_sum.append(prefix_sum[i] + arr[i])

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

다른 풀이 (boj book)

n,m = map(int,sys.stdin.readline().split())
arr = [0] + list(map(int,sys.stdin.readline().split()))
dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + arr[i]

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

시간초과 코드 O(n * m) - 구간합 방식

import sys

n,m = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))
for _ in range(m):
    i,j = map(int,sys.stdin.readline().split())
    sum = 0
    for idx in range(i- 1, j):
        sum += arr[idx]
    print(sum)

4. 알게된 점

📚 누적합 알고리즘 (Prefix Sum Algorithm)은 배열에서 특정 구간의 합을 효율적으로 계산하기 위한 기법입니다. 배열의 각 요소까지의 누적된 합을 계산하여 저장해두고, 이를 이용하여 구간 합을 O(1) 시간에 구할 수 있습니다.