[백준] #11659 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

📕 설명 📕

 

구간을 Indexing한 뒤, sum 함수를 이용해 풀이하였다.

 

그냥 indexing으로 sum을 하면 시간초과가 발생하므로,

 

prefix_sum 알고리즘을 사용해야한다.

 

새로운 배열에 값을 쌓는 형식으로 계속 더해서 넣은 후 indexing으로 값을 계산한다.

 

pypy로 실행하여 시간초과를 피하였다.

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

N, M = map(int, input().split())
N_list = list(map(int, input().split()))
tmp = 0
tmp_val = []
for i in N_list:
    tmp += i
    tmp_val.append(tmp)
for i in range(M):
    i, j = map(int,input().split())
    if i == 1:
        print(tmp_val[j-1])
    else:
        print(tmp_val[j-1] - tmp_val[i-2])