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

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

 

문제 분석

• 수 N개에 대해 i번째 수부터 j번째 수까지 합을 구하는 프로그램

 

코드 설계

• dp로 1~n까지의 합을 모두 구한 뒤,
• i부터 j까지의 합은 dp[j] - dp[i-1]

 

정답 코드

1차 - 시간초과

import sys
input = sys.stdin.readline

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

 

2차

import sys
input = sys.stdin.readline

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

dp = [0 for i in range(n+1)] # 1~n까지의 합
dp[1] = arr[0]

if n > 1:
    for i in range(2, n+1) :
        dp[i] = dp[i-1] + arr[i-1]

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