프로그래밍 공부/알고리즘
[백준] 11659 구간 합 구하기 4
99mini
2021. 10. 15. 21:02
반응형
SMALL
문제출처] https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
문제요약
1차원 배열 누적합(PREFIX SUM) 알고리즘 문제
풀이
누적합의 기본 알고리즘은 N부터 M까지의 합을 (M까지의 합) - (N까지의 합) 을 이용하여 계산하는 것이다.
소스코드는 Python 3으로 작성되었습니다.
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
numbers = list(map(int, input().split()))
prefix = [0 for _ in range(n+1)]
for i in range(n):
prefix[i+1] = prefix[i] + numbers[i]
for _ in range(m):
start, end = map(int, input().split())
print(prefix[end]-prefix[start-1])반응형
LIST