[알고리즘][백준] 11659. 구간 합 구하기 4

문제

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

 

문제 아이디어

숫자가 100000개, 케이스가 100000개 이므로 한 케이스 당 한 사이클의 개수를 더하면 시간 초과가 날 것입니다. 따라서 말 그대로 구간 합을 구해나가면 됩니다.

 

5 4 3 2 1 이 있다고 한다면, 아래와 같이 구할 수 있습니다.

1번째까지의 합: 5 = 5

2번째까지의 합: 5 + 4 = 9

3번째까지의 합: 5 + 4 + 3 = 12

4번째까지의 합: 5 + 4 + 3 + 2 = 14

5번째가지의 합: 5 + 4 + 3+ 2 + 1 = 15

 

그렇다면 이제 아래와 같이 생각할 수 있습니다.

2번째부터 4번째까지의 합: 4번째까지의 합 - 1번째까지의 합 (2번, 3번, 4번의 수를 더하는 것이므로 4번까지 다 더한 다음에 1번 값만 빼준다) = 14 - 5 = 9

즉 i 부터 j 까지의 합을 구하려면, j번째까지의 합 - (i - 1)번째까지의 합을 계산해주면 됩니다. 

 

import sys
input = sys.stdin.readline

N, M = list(map(int, input().split(' ')))
numbers = list(map(int, input().split(' ')))
dp = [0 for _ in range(N + 1)]
dp[0] = 0

for idx, number in enumerate(numbers):
    dp[idx + 1] = dp[idx] + number

for n in range(M):
    start, end = list(map(int, input().split(' ')))
    print(dp[end] - dp[start - 1])

import sys
input = sys.stdin.readline

이거 안하니까 입력 부분에서 시간 초과가 발생합니다. 시간 초과를 줄일 수 있는 방법입니다.