문제

N개의 수 A1, A2, …, AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A₁, A₂, …, A_N이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)

출력

총 M개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

풀이는 쉬운데, 시간초과 피하는 게 골치아프다.

i부터 j까지 구간의 합 = S_j - S_i-1인 점만 잊지 않으면 된다.

n+1개의 0으로 이루어진 리스트(ans)를 만들어, 맨 앞부터 구간별 합산 숫자를 해당 인덱스에 넣어준다. 그러면 ans[2]는 l[0]부터 l[2]까지 숫자의 합이 된다. 따라서 i부터 j까지 구간의 합은 ans[j]-ans[i-1]이다.

input()은 sys.stdin.readline()으로, print는 sys.stdout.write로 죄다 바꾸고, 언어도 pypy3으로 지정하고 나서야 겨우 시간초과 피하고 통과.

import sys
n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))
ans = [0] * (n+1) 
for i in range(1, n+1): # ans[0] = 0
    ans[i] = ans[i-1]+l[i-1] # 앞 숫자까지 합산한 값 + 해당 숫자
m = int(sys.stdin.readline())
for x in range(m):
    i, j = map(int, sys.stdin.readline().split())
    res = ans[j] - ans[i-1]
    sys.stdout.write(str(res) + '\n')

시간초과를 피하려면 결국 시간복잡도를 이해하고 고려해야 한다. 효율적인 시스템을 구현하는 방법이니까.

참고 : 입력 속도 비교

[문제 보기]

[비슷한 문제]