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

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

문제풀이

N, M : 입력값

arr : 입력 배열

sum_value : 누적 합

prefix_sum : 누적 합의 값들을 저장할 리스트

 

N 과 M 제한이 100,000이기에 O(NM)으로는 해결할 수 없다. 

구간 합을 효율적으로 구하기 위한 누적 합(Prefix Sum)을 통해 O(N+M)으로 효율적으로 해결할 수 있다.

 

1. sum_value에 배열의 원소들을 하나씩 더하면서 그 값을 prefix_sum 리스트에 저장한다.

 

2. i부터 j까지의 누적 합을 출력한다.

- i부터 j까지의 누적합은 prefix_sum[j] - prefix_sum[i] 이다.

 

코드

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))
    sum_value = 0
    prefix_sum = [0]

    for y in arr:
        sum_value += y
        prefix_sum.append(sum_value)
    for _ in range(M):
        i, j = map(int, sys.stdin.readline().split())
        print(prefix_sum[j] - prefix_sum[i - 1])

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!