[BOJ] 11659 | 구간 합 구하기 4

구간 합 구하기 4
https://www.acmicpc.net/problem/11659

 

 

 

 

작성 코드

 

import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(sum(nums[i-1:j]))

 

• 인덱스 슬라이싱을 통해 부분 배열을 구한 후 sum
• 시간 초과

 

 

이상 코드

 

누적 합

 

import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

sum_value = 0
sums = [0]

for num in nums:
    sum_value += num
    sums.append(sum_value)

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(sums[j]-sums[i-1])

 

• 각 인덱스 별 [:idx] 의 누적합 계산하여 활용

 

 

학습

 

• 누적합, 누적곱 등 누적 계산을 잘 활용하자