[백준 11659] 파이썬 - 구간합 구하기 4

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

11659번: 구간 합 구하기 4

 

1. 코드설명

import sys

input = sys.stdin.readline

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

arr = list(map(int,input().split()))

# 첫번째 수부터 n 번째 수까지 합을 list 행태로 저장

# arr = [5, 4, 3, 2, 1]

# sum_arr = [0, 5, 9, 12, 14, 15]

sum_arr = [0]*(n+1)

for i in range(1,n+1) : 

  sum_arr[i] = sum_arr[i-1]+arr[i-1]

# 2, 5 인 경우 sum_arr의 5번째 인덱스 - 두번째 인덱스 = 2~5까지 합

for k in range(m) :

  i, j = map(int,input().split())

  print(sum_arr[j] - sum_arr[i-1])

 

2. 주의 사항

for k in range(m) :

  i, j = map(int,input().split())

  print(sum_arr[j] - sum_arr[i-1])

 

이런식으로 input 마다 sum을 해주는 방식은

 

간단하지만 시간초과가 발생한다.

 

 

따라서 먼저 합계 리스트(sum_arr)를 구하고 그것을 출력하는 형태로 문제를 접근해야한다.