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

Python 코드

n, m = map(int, input().split())
numbers = list(map(int, input().split()))
sum = [0]
tmp = 0

# 누적 합 구하기
for i in numbers:
    tmp = tmp + i
    sum.append(tmp)

# 구간 합 구하기
for _ in range(m):
    i, j = map(int, input().split())
    print(sum[j] - sum[i-1])

Python 코드 풀이

이번 문제는 구간 합을 구하는 문제입니다. N과 M의 최대 횟수는 각각 100,000이기 때문에 시간 복잡도를 고려해야 합니다.

완전 탐색 알고리즘으로 풀게 되면 시간 초과가 발생할 수 있습니다. 그래서 누적합 기법을 사용하여 합 배열을 미리 구해놓으면, 구간 합을 O(1) 시간 복잡도로 구할 수 있습니다.

원본 리스트를 A, 누적 합 리스트를 S라고 할 때,

1. 누적 합 구하기: S[i] = S[i-1] + A[i]
2. 구간 합 구하기: S[j] - S[i-1]

문제에서 주어진 구간 합을 구할 대상 배열은 [5, 4, 3, 2, 1]이고, 이 배열에서 [1, 3], [2, 4], [5, 5] 구간의 합을 구하려고 합니다.

인덱스 번호는 0부터 시작하지만, 문제에서는 1부터 시작한다고 명시하였습니다.

따라서, 대상 배열을 누적하여 tmp 변수에 저장하고, 이 값을 sum 리스트에 추가하면 누적 합 리스트 sum을 얻을 수 있습니다.

구간 i, j를 입력 받아서, 구간 합 구하기 공식인 S[j] - S[i-1]를 사용하면 해당 구간의 합을 구할 수 있습니다.