BOJ_11659 : 구간 합 구하기 4

👉 문제링크

11659번: 구간 합 구하기 4

---

---

🔸 문제 분석 🔸

• 숫자 리스트를 입력받고, 특정 구간에 대한 합을 출력한다.

🔸 코드 🔸

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
acc = [0]

for i in arr:
    acc.append(acc[-1] + i)

for _ in range(m):
    start, end = map(int, sys.stdin.readline().rstrip().split())
    sys.stdout.write(str(acc[end] - acc[start-1]) + "\n")

🔸 코드 해석 🔸

• n, m의 범위가 10만이고, 제한시간이 1초여서 빠른 입출력을 사용했다.
• 시간안에 누적 합을 계산하기 위해서 미리 리스트의 원소를 순차적으로 누적한 acc 리스트를 계산해둔다.
  • -1 인덱스를 사용하고, 입력 인덱스와 값을 맞추기 위해 초기값 0을 넣는다. 
  • 인덱스 start ~ end 의 합은 누적 리스트에서 end번 원소 - (start-1)번원소이다

 

---

🔸 end 🔸

• 첫 풀이에서 그냥 리스트 슬라이싱에 sum()함수로 합을 구하니 시간초과가 나왔다.
• 문제의 태그가 누적 합이어서 미리 계산해두는 것 같아 규칙을 생각해보니, 풀이를 떠올릴 수 있었다.
• 누적 합 태그는 아주 간단한 문제들만 봤었는데, 이제 점점 난이도가 올라가나 싶다.
• 검색하지 않고 풀이에 성공한게 뿌듯하다.