백준 11659 - 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

처음에는 무식하게 아래와 같이 풀어서 냈다,

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

그리고 시간초과를 먹었다. 이런 문제는 대부분 미리 arr_sum과 같이 구간합을 계산해 놓은 뒤에, input값이 들어왔을 때 해당 구간합 값을 호출하거나 빼 주는 식으로 문제를 풀어야 한다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr_sum = [0]*n
for i in range(n):
    if i == 0:
        arr_sum[i] = arr[i]
    else:
        arr_sum[i] = arr_sum[i-1] + arr[i]

for i in range(m):
    x,y = map(int, input().split())
    if x==1:
        print(arr_sum[y-1])
    else:
        print(arr_sum[y-1]-arr_sum[x-2])

여담으로 이 문제는 일반적인 input으로는 시간초과에 걸리게 된다. 꼭 sys.stdin.readline을 호출할 것.