(Python) 백준 11659

백준 11659

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	57629	24589	18978	41.178%

문제

수 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

---

답안

import sys

n, m = map(int, sys.stdin.readline().split())
numbers = [0] + list(map(int, sys.stdin.readline().split()))

for i in range(1, n+1):
    numbers[i] += numbers[i-1]

for i in range(m):
    range_start, range_end = map(int, sys.stdin.readline().split())
    print(numbers[range_end] - numbers[range_start-1])

풀이

https://www.youtube.com/watch?v=Ppuj5gw78Vc&ab_channel=KhanAcademy

이 동영상을 보면 수열의 부분합을 이용해 특정 원소가 무엇인지 구할 수 있다.

이와 비슷하게, $i$번째부터 $j$번째까지의 수열의 부분합을 구하고자 한다면, $S_1$, $S_2$, $S_3$, … 의 배열을 만든 뒤 $S_j - S_{i-1}$ 을 통해 구할 수 있다.

n, m = map(int, sys.stdin.readline().split())
numbers = [0] + list(map(int, sys.stdin.readline().split()))

numbers 리스트에서는 구현의 편리함을 위해 0을 첫 번째 element로 두었다.

이로써 문제 조건의 n번째 수와 리스트에서의 n번째 수가 같아지게 되었다.

for i in range(1, n+1):
    numbers[i] += numbers[i-1]

for i in range(m):
    range_start, range_end = map(int, sys.stdin.readline().split())
    print(numbers[range_end] - numbers[range_start-1])

numbers 배열을 첫 번째 element부터 자기 자신 element까지의 합 배열으로 만든다.

numbers 배열의 j번째 수 - i-1번째 수, 즉 i번째부터 j번째 수까지의 합을 출력한다.