[ BOJ / 파이썬 ] 11659 구간 합 구하기 4

아 나는 확실히 PS를 잘 못 풀고 있었던 것일까?

아니면 시간을 들였기 때문에 이제야 문제 푸는 느낌나게 푸는건가? 이제야 뭔가 로직이 로직답게 만들어지는 것 같다.

 

0) 문제 정의

n개의 문자 배열 중에

i , j 받았을 때 i~j 범위의 문자 배열 값들의 합

 

 

1) DP테이블 정의

dp[n]은 n까지의 num들의 합

dp[j] = dp[j-1] + num[j]

 

2) 점화식 구하기

보통 순차적인 합이 있을 때, 특히 DP테이블의 누적 합이므로

dp [j] ~ dp[i] = dp[j] - dp[i-1]

 

3) 초기값

dp[0] = 0으로 해주고, num에 따라서 합을 누적해서 넣어서 dp테이블 채우기.

 

/  첫 번째 제출  /

import sys
input = sys.stdin.readline

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

num = list(map(int, input().split()))
dp = [0] * n

for i in range(n):
  dp[i] = dp[i-1]+num[i]
  
for i in range(m):
  i, j = map(int, input().split())
  i = i - 1
  j = j - 1
  if i - 1 >= 0:
    print(dp[j] - dp[i-1])
  else:
    print(dp[j])