구간 합 구하기 4, boj11659, 백준, python

구간 합 구하기 4 

시간	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	56629	24204	18693	41.232%

문제

수 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

예제 출력 1 복사

12
9
1

 

 

 

문제풀이

주어진 숫자 리스트에 구간 합을 구하는 문제이다. 처음 문제를 풀이할 때, 인덱스로 접근하여 구간합을 그때 마다 구해주었는데 이렇게 풀이를 할 경우 매번 같은 작업을 반복하게 되므로 효율성 면에서 떨어지게 된다. 제출을 하여도 물론 시간 초과가 생기게 된다.

 

그렇다면 이 작업을 효율적으로 하려면 어떻게 해야할까?

 

주어진 숫자들의 누적 합을 리스트에 저장해 두고, 각 자리의 누적합을 빼는 방식으로 처리한다면 같은 작업 반복 없이 뺄셈만으로 정답이 도출이 가능하다!. 코드는 다음과 같다.

 

# 구간 합 구하기 4

import sys


n,m = map(int,sys.stdin.readline().split())
n_arr = list(map(int,sys.stdin.readline().split()))
# [5, 4, 3, 2, 1]

# 누적합을 저장해 놓을 리스트를 만든다.
sum_arr = [0 for _ in range(n+1)]

# 누적합을 저장한다.
for i in range(1, n+1):
    sum_arr[i] = sum_arr[i-1] + n_arr[i-1]


# 누적 리스트에 접근하여 구간합을 계산해 준다.
for _ in range(m):
    first, end = map(int, sys.stdin.readline().split())
    print(sum_arr[end]-sum_arr[first-1])