[백준] 11659 : 구간 합 구하기 4 (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/11659

문제

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

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

입력

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

출력

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

예제

입력

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

출력

12
9
1

---

정답 및 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = list(map(int, input().split()))

prefix = [0] * (n + 1)

for i in range(n):
    prefix[i + 1] = prefix[i] + nlist[i]

for _ in range(m):
    i, j = map(int, input().split())
    print(prefix[j] - prefix[i - 1])

1. import sys
   • 파이썬 기본 입력보다 빠른 입력 처리를 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • 입력 데이터가 많을 때 시간 초과를 방지하기 위해 input()을 readline()으로 재정의한다.
3. n, m = map(int, input().split())
   • n은 수열의 길이이다.
   • m은 구간 합을 구해야 하는 횟수이다.
4. nlist = list(map(int, input().split()))
   • 실제 구간 합을 계산할 원본 수열이다.
   • 인덱스는 0부터 시작한다.
5. prefix = [0] * (n + 1)
   • 누적합(prefix sum)을 저장할 배열이다.
   • prefix[0] = 0을 미리 만들어 계산을 단순화한다.
   • 문제에서 구간이 1번부터 시작하므로 배열 크기를 n + 1로 설정한다.
6. for i in range(n):
   • 수열의 모든 원소를 순회하며 누적합을 계산한다.
7. prefix[i + 1] = prefix[i] + nlist[i]
   • 이전까지의 누적합에 현재 값을 더한다.
   • prefix[i + 1]은 nlist[0]부터 nlist[i]까지의 합이다.
8. for _ in range(m):
   • 총 m번의 구간 합 질의를 처리한다.
9. i, j = map(int, input().split())
   • 구간의 시작 인덱스 i와 끝 인덱스 j를 입력받는다.
   • 문제 기준 인덱스는 1부터 시작한다.
10. print(prefix[j] - prefix[i - 1])
    • 누적합 공식으로 구간 합을 계산한다.
    • prefix[j] - prefix[i - 1]은 i ~ j 구간 합이다.

---