[백준/Python] 11659번 : 구간 합 구하기 4

문제 정보

제목 : 구간 합 구하기 4

번호 : 11659번

사용 언어 : Python

문제 링크

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

11659번: 구간 합 구하기 4

 

시간 제한	메모리 제한
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

 

입출력 예제

---

나의 풀이

누적합 알고리즘을 이용했습니다. map함수를 이용해 첫째 줄의 숫자 두개를 입력받고, 둘째줄에 입력받은 수를 list의 형태로 저장했습니다. list_N에 하나씩 접근하는 for 루프를 통해 인덱스별 누적된 합을 저장합니다. 그리고 합을 구하는 횟수만큼 반복하는 for루프를 이용해 i번째부터 j번째까지의 누적합을 구했습니다. ( sum_N[j] - sum_N[i-1] )

 

코드

import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 수의 개수 N, 합을 구해야하는 횟수 M
list_N = list(map(int,input().split())) # N개의 수를 리스트로 저장함
sum_N = [0] # 누적 합을 구할 리스트
tmp_sum = 0

for i in list_N : # 각 구간별 누적합을 구하여 리스트에 저장함
    tmp_sum += i
    sum_N.append(tmp_sum)

for i in range( M ) : # M번 반복하며 j번째 수의 누적합 - i번째 수의 누적합을 구하여 출력함
    i , j = map(int,input().split())
    print(sum_N[j] - sum_N[i-1])