백준 BAEKJOON 11441번 합 구하기 [PYTHON/파이썬]

 

 

 

 

 

백준 BAEKJOON 11441번 합 구하기 [PYTHON/파이썬]

---

<문제 출처> (SILVER Ⅲ)

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

11441번: 합 구하기

 

 

 

 

 

<풀이>

누적합을 이용해서 풀면 된다.

먼저 원본 배열을 기준으로 누적합을 담을 배열을 담는다.

k번째 인덱스의 누적합을 구하는 공식은

k-1번째 누적합에서 원본 배열의 k번째 인덱스를 더한 것과 같다.

S[k] = S[k - 1] + A[k]

 

이렇게 만들어진 누적합 배열에서

원본 배열의 i번째 인덱스부터 j번째 인덱스까지의 합은

누적합 S의 j번째 인덱스에서 i-1번째 인덱스를 빼주면 된다.

S[j] - S[i - 1]	# i번째 수 부터 j번째 수까지의 합

 

 

 

 

 

<코드>

import sys

input = sys.stdin.readline
N = int(input())
A = [0] + list(map(int, input().split()))
S = [0] * (N + 1)

for k in range(1, N + 1):
    S[k] = S[k - 1] + A[k]

M = int(input())

for _ in range(M):
    i, j = map(int, input().split())
    result = S[j] - S[i - 1]
    print(result)