[DP] 11659번 구간 합 구하기4 - 실버3

[heerucan]

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

import sys 

n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

D = [0] * 100000
a = 0
for i in range(0, n):
    a += data[i]
    D[i] += a

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    if i >= 2:
        print(D[j-1]-D[i-2])
    else:
        print(D[j-1])

시간초과 이슈

• import sys로 해결
• data = list(map(int, input().split())) 은 아래와 같음
• data = list(map(int, sys.stdin.readline().split()))

생각

• 문제에서 구하라는 값은 i번째 수 ~ j번째 수까지의 합인데, 그말은 즉, j번째 수까지의 합에서 i-1번째까지의 합을 빼면 된다.
• 그러면 D[n] = n번째 수까지의 합이 메모되어서 들어가야 하고,
• 배열 0번부터 값을 메모하기 때문에 이전 문제들과 다르게 D[0]부터 올바르게 써준다. 그로 인해 문제에서 요구하는 i/j번째 수와 배열의 인덱스의 오차로 생기는 이슈를 고려해야 한다.

점화식은?

• D[j-1]-D[i-2]
• 여기서 고려하지 못해서 초반에 틀린 게 1 ≤ i ≤ j ≤ N 즉, i가 1인 경우, D[i-2]는 D[-1]이 되어 배열의 가장 마지막 값을 불러온다. 글서 분기처리를 해줬다.