[백준] 11659 구간 합 구하기4 (Python 파이썬)

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

11659번: 구간 합 구하기 4

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

---

풀이 과정

이 문제는 

누적 합 으로 푸는 문제이다.

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

 

한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류가 나게 된다.

 

그래서 매번 구간합을 구하는 것이 아니라,

처음에 n개의 수를 입력받고 나면

길이 n짜리 리스트를 만들어 리스트의 각 자리에 그 자리까지의 누적합을 저장한 후에

각 자리의 누적합에서 빼주는 방식으로 구간합을 구하면 된다.

 

예를 들어 2 ~ 4 구간합을 구한다면

4까지의 구간합에 2 이전 까지의 구간합을 빼면 되는 것이다.

 

이 때, 주의해야 할 점은

2 ~ 4 구간합이라고 하면 4까지의 구간합에 2 이전까지의 구간합이므로

맨 처음 리스트에 0을 넣어 인덱스를 맞춰주어야 한다.

 

맨 앞에 0을 붙여주자.

 

이를 파이썬코드로 나타내면 다음과 같다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
pre = [0]
mysum = 0

for i in range(n):
  mysum += nums[i]
  pre.append(mysum)


for i in range(m):
  a, b = map(int, input().split())
  print(pre[b] - pre[a-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !