(Python/🥈2)백준리즘알고 11441번: 합 구하기

 

문제 바로가기 

합 구하기

문제:

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

입력:

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

출력:

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

 

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


n = int(input())
lst = list(map(int,sys.stdin.readline().rstrip().split(" ")))
m = int(input())
arr = [list(map(int,sys.stdin.readline().rstrip().split(" "))) for _ in range(m)]

dp = [0] * (n+1)
for i in range(1,n+1):
    dp[i] = dp[i-1] + lst[i-1]
for left, right in arr:
    if left == right:
        print(lst[left - 1])
    else:
        print(dp[right] - dp[left - 1])

 

누적합 알고리즘이다.

dp 에는 1부터 시작해서 누적 합을 저장했다.

1,2,3,4,5 일경우 1 3 6 10 15 이렇게 dp 에 저장한다.

arr 에서 left, right 값을 꺼낸후 2 부터 5 일경우에는 1까지의 합이 필요 없으므로

5까지의 합 - 1까지 합을 빼주면 된다.

만약 left와 right 가 같게 되면 그냥 그 자체를 뽑아주면 된다 .