백준 파이썬 11659번 구간 합 구하기 4 (Today I Learn 2025.02.01)

백준 파이썬 공부 2025.02.01
11659번 구간 합 구하기 4 (실버 3)

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

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

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

4. 제한
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
- 1 ≤ i ≤ j ≤ N

5. 문제 풀이
일단 단순 sum 함수를 사용하여 풀어보자
>>> 코드1. 단순 함수 사용 >> 시간초과

import sys

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

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(sum(num[a-1 : b]))

흠 되긴 하나 실행시간이 너무 오래 걸려 시간초과가 걸린다..
그럼 다음 방식으로 누적합을 써보자
누적합을 이용하여 각각의 인덱스 까지의 합을 계산해서 저장해놓고
(j까지의 합) - (i-1까지의 합) 방식으로 계산해보자

>> 코드 2. 누적 합 계산

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

dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = dp[i-1] + num[i-1]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(dp[b] - dp[a-1])

저장 공간과 실행 시간은 확실히 별개라는걸 다시한번 느끼게 된다.

6. 문제 링크
https://www.acmicpc.net/problem/11659