[백준 / #11659] 구간 합 구하기 4 (Python)

문제 설명

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

11659번: 구간 합 구하기 4

 

 

 

 

---

문제풀이

 

DP를 공부하고 있으니 DP 문제인 걸 알았지만, 그냥 이 문제를 봤을 때 DP로 방향을 잡을 수 있을지는 모르겠다..

처음에는 2차원 DP로 풀었다. DP[i][j] 에 i부터 j까지의 합을 구해서

i == j ) DP[i][j]  =  num[j-1]

else) DP[i][j] = dp[i][j-1] + num[j-1]

당연하게도 시간초과가 나버림.. why? n이 100,000까지 가능 ㅋㅋ o(n^2)이면 10억..


그래서 생각을 해보니 1차원으로도 가능했다.

첫번째 수부터 각 인덱스 번째 수까지 더한 값을 저장하고 DP[j] - DP[i-1] 하면 쉽게 해결했다.?

나중에 보니 이게 ?prefix sum이라고 효율적으로 계산하는 방법이라더라 ㅋㅋ

이 방식 기억해 놓아야겠다!?

import sys
input = sys.stdin.readline

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

num = list(map(int, input().split()))
dp = [0 for _ in range(N+1)]
dp[1] = num[0]
for i in range(2, N+1):
    dp[i] = dp[i-1] + num[i-1]

for _ in range(M):
    i, j = map(int,input().split())
    print(dp[j] - dp[i-1])