[BOJ | Python] 11441번: 합 구하기

https://www.acmicpc.net/problem/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개의 줄에 걸쳐 입력으로 주어진 구간의 합을 출력한다.

 

풀이

input = __import__('sys').stdin.readline

N = int(input())
A = list(map(int, input().split()))
prefix = [0] * N

for i in range(N):
    prefix[i] += prefix[i - 1] + A[i]

for _ in range(int(input())):
    i, j = map(int, input().split())
    if i - 2 < 0: print(prefix[j - 1])
    else: print(prefix[j - 1] - prefix[i - 2])

 

누적합을 구하는 전형적인 문제!

여기서는 N과 M이 모두 10만이므로 만약 모든 [i, j]를 일일히 계산한다면 시간초과가 발생할 것이다.

따라서 prefix라는 배열에 특정 인덱스까지의 누적합을 저장한 후, 구간 [i, j]의 합을 구할 때는 j까지의 누적합에서 i-1까지의 누적합을 빼는 식으로 구할 수 있다.

 

다만 빠른 입력을 받지 않으니 파이썬으로는 시간초과가 발생했다...ㅜㅜ

 

input = __import__('sys').stdin.readline

이 코드는 파이썬에서 입력을 빠르게 받는 방법이다.

일반적인 input()보다 훨씬 빠르기 때문에, 입력이 많을 때는 필수적인 수준이라고 한다.

따라서 위 코드는 input() 함수를 sys.stdin.readline으로 덮어쓰기 해서 이후 input()을 쓸 때 더 빠르게 입력을 받을 수 있도록 하는 것이다.