[백준 11659번] 구간 합 구하기 4

11659번: 구간 합 구하기 4

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

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

answers = []

dp = [0]*(n+1)

for i in range(1,n+1):
    dp[i] = dp[i-1] + numbers[i-1]

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

    answers.append(dp[j]-dp[i-1])

for answer in answers:
    print(answer)

 

이번 문제는 주어진 n개의 수 중에서 i 부터 j 번째까지의 합을 구하는 문제이다.

 

시간복잡도를 고려하지 않고 풀이하면 굉장히 간단한데, M번에 걸쳐서 들어오는 질의에 대해 A[i] + A[i+1] + ... + A[j]를 계산해서 출력하면 된다.

 

N과 M이 최대 100,000이기 때문에 시간복잡도는 O(NM)이다. 따라서 N, M의 크기를 생각해봤을 때 N×M은 100억이니 시간초과가 발생하게 된다.

 

따라서 DP를 사용하여 풀이하는 방법을 생각해볼 수 있는데, 처음에는 2차원 배열로 선언하여 풀었다가 메모리 초과가 발생함과 동시에 1차원 배열로도 해결할 수 있다는 것을 깨닫고 1차원 DP 테이블로 해결하였다 :)