[파이썬, Python] 백준 11659 : 구간 합 구하기4

백준 11659 : 구간 합 구하기4

📖 문제 📖

 

 

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

 

---

📺 입력&출력 📺

---

📝 풀이 📝

문제를 요약하자면

5 4 3 2 1 이렇게 입력값이 들어오고, 1 3 으로 들어왔을때 첫번째 인덱스에서 세번째 인덱스까지의 합을 구해서 출력하는 문제라고 이해하면 됩니다.

 

일반적으로 풀면,

1번 인덱스부터 3번 인덱스까지 합을 구하라고 할 때

5 + 4 + 3 과 같이 계속 연산을 해야합니다.

1번 인덱스부터 5번 인덱스까지 합을 구하라고 할 때

5 + 4 + 3 + 2 + 1 과 같이 계속 연산을 해야합니다.

 

이 방법대로 했을 때 비록 구현하기 간단하지만 N이 최대 100,000까지이고 M도 최대 100,000까지이기 때문에 최악의 경우 일반적인 방법으로는 시간초과가 나는 문제입니다.

 

그렇기 때문에 더욱 효율적인 방법으로 풀어야합니다.

 

여기에서 쓰이는 방법이 누적합(Prefix Sum)입니다.

한마디로 설명하자면, 한번 모든것을 다 계산하고, 필요한 부분만 찾아서 쓰자! 라는 개념이라고 할 수 있습니다.

 

이 문제에 적용 해 본다면 

5 4 3 2 1을 누적하여 합을 구하면 5 9 12 14 15가 됩니다.

이랬을 때

2번 인덱스 부터 4번 인덱스까지 합을 구하라고 하면

4번까지의 누적합 인덱스에서 1번까지의 누적합 인덱스를 빼주면 구할 수 있습니다.

---

👨‍💻 나의 코드 👨‍💻

import sys
n,m = map(int,sys.stdin.readline().split())
arr = [0]
arr.extend(list(map(int,sys.stdin.readline().split())))
arr.append(0)
for i in range(1,n+1):
    arr[i] = arr[i-1]+arr[i]
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    print(arr[b]-arr[a-1])