[BOJ][Python] 11659 구간 합 구하기 4

Overview

• 체감 난이도: ★☆☆☆☆
• 문제 레벨: 실버 3
• 문제 유형: 누적 합
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

 

[코드]

처음에는 단순하게 문자열 슬라이싱의 합을 구했는데 예상했다시피 시간 초과가 발생했다. 

새로운 배열을 생성해 누적합을 저장해주었고, 범위에 벗어나는 값을 빼주었다. // 시간복잡도: O(n + m)

>> 이렇게 해도 시간 초과가 났다.  입출력 속도 문제일까 싶어서 sys.stdin.readline 해주었는데 성공 ! 

import sys
input = sys.stdin.readline

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

pre = [0] * (n+1)
for p in range(1, n+1):
    pre[p] = pre[p-1] + arr[p-1]

for t in range(m):
    i, j = map(int, input().split())
    print(pre[j] - pre[i-1])