[Baekjoon 11441 / Python / 실버3] 합 구하기

문제

import sys

input = sys.stdin.readline

N = int(input())

numbers = list(map(int, input().split()))

M = int(input())

result = [0 for _ in range(N + 1)] # 입력값과 인덱스를 맞추기 위해 + 1

result[1] = numbers[0]

for i in range(2, N + 1):

    result[i] = result[i-1] + numbers[i-1]

for _ in range(M):

    i, j = map(int, input().split())

    if i == 1:

        print(result[j])

    else:

        print(result[j] - result[i-1])

 

누적 합 알고리즘을 그대로 사용하면 되는 문제이다.

 

마치 DP테이블을 만드는 것 처럼, result 리스트에 미리 0번~ 특정 인덱스까지의 합을 구해놓는다.

1번부터 n번까지의 합을 구하려면 n번 인덱스에 저장된 값을 출력하면 되고,

3번부터 n번까지의 합을 구하려면 n번 인덱스에 저장된 값에서 2번에 저장된 값을 빼주면 된다.

 

이 문제는 숫자 N이 10만개, 계산해야 할 구간 M도 10만개 이기 때문에 단순 반복문으로 풀 경우 최악 복잡도가 O(N^2)이 되므로, 연산 횟수가 [10만 * 10만 -> 100억] 까지도 갈 수 있다. 따라서 누적 합 알고리즘으로 풀어야 시간초과가 나지 않고 해결할 수 있다.

 

결과