백준 11659번 구간 합 구하기 4

정보

문제 바로가기 [클릭]

난이도: Silver3

관련 개념: #누적합

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

---

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

---

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

예제 입출력 1

입력

5 3
5 4 3 2 1
1 3
2 4
5 5

출력

12
9
1

---

코드(파이썬)

import sys

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

nums_sum = [nums[-1]]
for i in range(n-2, -1, -1):
    nums_sum.append(nums_sum[n - i - 2] + nums[i])
nums_sum = nums_sum[::-1]

for s, e in [map(int, line.split()) for line in sys.stdin.readlines()]:
    if e == n:
        print(nums_sum[s-1])
    else:
        print(nums_sum[s-1] - nums_sum[e])

---

특이사항

• 미리 합을 계산하고, 그 값을 이용하는 방식 사용
• 내 코드(88,516KB, 420ms)에 비해 우수한 코드(바로가기, 33,800KB, 92ms)와 비교

  • import sys
    
    n, m =map(int,input().split())
    s = list(map(int, input().split()))
    ss =[0]
    for i in s:
        ss.append(ss[-1]+i)
    
    for i in range(m):
        a, b =map(int, sys.stdin.readline().split())
        print(ss[b]-ss[a-1])
    

  • 동일한 개념
  • 자료구조
    • 기존: 2개의 리스트
    • 개선: 1개의 리스트
  • 합 계산
    • 기존: 2가지 경우로 나눠 계산
    • 개선: 조건문 없이 바로 계산

---

참고문헌

• kim.svadoz, “개념-52-Prefix-Sum누적-합-구간-합”, programmer life guidance 101, https://coder-in-war.tistory.com/entry/개념-52-Prefix-Sum누적-합-구간-합
• 코딩무식자 전공생, “누적합(prefix sum)”, 코딩무식자 전공생, https://jow1025.tistory.com/47