[구현/수학] 백준 11441 합 구하기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11441번: 합 구하기

 

 

 

2. 문제 풀이

 주어진 수열의 구간 합을 구하는 문제입니다.

 

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

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

 구간 합 구하기 4와 동일한 문제입니다. '누적합'을 이용해서, i부터 j까지의 구간 합을 [ j까지의 누적 합 - (i-1)까지의 누적 합 ]으로 구합니다.

 최대 100000번까지 구간 합을 구해야 하므로, 반복되는 계산을 피하고자 미리 누적 합을 구해두고 빼는 방식을 사용합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

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

# 누적 합 구하기
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])

 [ i ~ j까지의 구간 합 = j까지의 누적 합 - (i-1)까지의 누적 합 ] 을 그대로 구현합니다.