[구현/수학] 백준 11659 구간 합 구하기 4 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11659번: 구간 합 구하기 4

 

 

 

2. 문제 풀이

 길이 N의 수열이 주어졌을 때, 구간 합을 구하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 단순히 매번 구간 합을 구하면 '시간 초과'가 납니다. M이 최대 100000이기 때문에, 구간 합을 미리 구해서 동일한 계산을 반복하지 않도록 해야 합니다.

 

수열	3	5	2	1	3	-1
처음부터 자신까지의 합 [누적 합]	3	8	10	11	14	13

 방법은 간단합니다. 미리 누적 합을 구해둡니다. 그리고 i부터 j까지의 구간 합을 [ j까지의 누적 합 - (i-1)까지의 누적 합] 으로 구합니다. 

 간단한 수학 트릭이지만, 요즘은 SW적성검사 등에서도 자주 나오니 알아두시면 좋습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
numlist = list(map(int, input().split()))

# 누적 합 구하기
sumlist = [0]
_sum = 0
for i in range(N):
    _sum += numlist[i]
    sumlist.append(_sum)

# 구간 합 출력
for _ in range(M):
    start, end = map(int, input().split())
    print(sumlist[end] - sumlist[start-1])

 0부터 N까지의 누적 합을 구해 리스트에 저장합니다.

 i부터 j까지의 구간 합은 [ j까지의 누적 합 - (i-1)까지의 누적 합 ] 으로 구합니다.