백준 11659 - 구간 합 구하기 4 (Python3)

코드

import sys
input = sys.stdin.readline

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

num = list(map(int, input().split()))

d = [0] * (N+1)

for i in range(1, N+1):
    d[i] = d[i-1] + num[i-1]
    
for _ in range(M):
    i, j = map(int, input().split())
    
    answer = d[j] - d[i-1]
    
    print(answer)

문제 해설

동적 프로그래밍 참고

DP 문제이다. 처음 접근했을 때 문제가 너무 간단해서 리스트 Slicing으로 간단하게 풀었느나 당연히 시간 초과가 발생했다.DP 테이블에 i, j번째 까지의 합을 저장한 후, j번째까지 합 - i번째까지 합을 구해주면 정답이다.