[Python/파이썬] 백준 11659 - 구간 합 구하기 4

문제 설명

 

입출력 예제

 

---

풀이 코드

이 문제는 현대오토에버 코딩문제에 나온 문제라고 한다.

사실상 실버난이도인 만큼 접근만 한다면 쉽게 풀 수 있는 문제다.

제한 사항을 보면 N, M 입력값의 제한 범위가 100,000이다.

이중 반복문으로 풀면 쉽게 풀수는 있겠지만 2중 반복문은 O(n^2) 시간 복잡도를 갖기 때문에 시간초과가 발생한다.

따라서 O(N)이나 O(logN)의 시간 복잡도로 풀어야 하는데

문제에서도 이미 정답을 말해줬다."구간합"

 

문제를 푸는 방법은 다음과 같다.

1. 주어진 값들의 누적합을 갖는 리스트를 만든다. PrefixSum
2. 여기서 PrefixSum에 0을 넣어 놓은 이유는 주어지는 구간 i가 1부터 시작하기 때문에 인덱싱에러를 방지하기 위해서이다.
3. 각 수들의 합을 갖는 변수 total을 prefixSum에 추가하여 누적합 리스트를 완성한다.
4. 구한 누적합들을 이용해 구간 합을 구하는 공식 prefixSum[rifght] - prefixSum[left - 1] 을 사용해 구간합을 구한다.

 

정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 개수, 합
nums = list(map(int, input().split()))
total = 0 # 각 수의 합 저장
prefixSum = [0] # 구간합 저장 리스트

for i in nums:
    total += i
    prefixSum.append(total)

for _ in range(m):
    i, j = map(int, input().split())
    print(prefixSum[j] - prefixSum[i - 1])