11659 - 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

- 메모이제이션 (구현)

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nl = [0] + list(map(int, input().split()))
sl = [0] * (n+1)
for i in range(1, n+1):
    sl[i] = sl[i-1] + nl[i]

for _ in range(m):
    i, j = map(int, input().split())

    print(sl[j] - sl[i-1])

 

첨엔 그냥 슬라이싱으로 풀어서 제출했는데, 당연히 안됐다 (시간 초과)

실버3이면 더 어렵게 생각해야되는데 ㅎㅋㅋ

 

쨋든 첫 번째 수부터 k 번째 수까지의 합을 갖는 sl 리스트를 만들어서 해결했다.

그 전 값에 k 번째 수를 더하는 메모이제이션을 이용해서 시간을 단축시켰다!