[11659] 구간 합 구하기 4 (Python)

문제

---

11659번: 구간 합 구하기 4

시간초과 해결하기 위한 흔적들

 

틀린 코드

---

N,M = map(int,input().split())

num_list = [-1]+list(map(int,input().split()))

for _ in range(M):
    start_index,end_index = map(int,input().split())
    print(sum(num_list[start_index:end_index+1]))

 

문제 풀이

---

처음 이 문제를 단순 구현으로 생각해서 시간초과가 났었습니다.

 

 

정수 범위를 확인하지 않은 탓인데, N과 M이 각각 10만까지 이므로 이전과 같이 단순 구현으로 구하면 O(N)이 10**10 이 됩니다.

시간 초과가 안나면 이상한 상황.

 

그래서 다르게 접근 하기로 했습니다.

다이나믹 프로그래밍처럼 값들을 미리 저장해 두고 그 값들을 참조하면 되겠다 싶었습니다.

 

정답 코드

---

import sys
input= sys.stdin.readline
N,M = map(int,input().split())

num_list = [0] + list(map(int,input().split()))

accumulate_sum = [0]
for i in range(1,N+1):
    accumulate_sum.append(accumulate_sum[i-1]+num_list[i])

for _ in range(M):
    start_index,end_index = map(int,input().split())
    print(accumulate_sum[end_index]-accumulate_sum[start_index-1])

 

num_list와 accumulate_sum의 처음 원소를 0으로 부여한 것은 입력 값들이 1부터 시작하므로 그에 맞추도록 했고 합에는 영향을 미치지 않게 하기 위해 0을 부여했습니다.