[백준] 11659번 : 구간 합 구하기 4 (파이썬)

문제

오답

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
arr=list(map(int,input().split()))
for _ in range(m):
    i,j=map(int,input().split())
    print(sum(arr[i-1:j]))

나의 최종 답안(정답)

import sys
input = sys.stdin.readline

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

dp=[0]*(n+1)#인덱스 혼동 때문에 n+1로(인덱스 0은 0으로 사용x)
for k in range(1,n+1):
    dp[k]=dp[k-1]+arr[k-1]#합 미리 구하기
for _ in range(m):
    i,j=map(int,input().split())
    print(dp[j]-dp[i-1])#j번째~i번째

만만하게 봤다가 계속 틀린 문제

접근 방법

• 그냥 배열 인덱스의 합을 구해주면 시간초과가 난다. 따라서 dp로 풀어주었다.
• 입력받은 숫자의 누적합을 dp에 저장한다.
• i, j를 입력받고 해당하는 값의 합을 출력해준다.