Algorithm/Implementation
[백준] 11659 구간 합 구하기4 (Python 파이썬)
안드선생
2022. 5. 17. 15:54
반응형
https://www.acmicpc.net/problem/11659
문제 설명
수 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])
전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
반응형