[ 알고리즘 ] 백준 11659번: 구간 합 구하기 4

이주 weekwith.me·2022년 8월 12일

알고리즘

목록 보기

60/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 11659번: 구간 합 구하기 4를 풀고 작성한 글입니다.

문제

설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

풀이

접근법

접두사 합계(Prefix Sum) 알고리즘을 활용해서 문제를 해결할 수 있다.

이때 제시되는 i번째 수부터 j번째 수가 인덱스와 동일하게 0부터 시작하는 것이 아닌 1부터 시작하기 때문에 최종적으로 계산 결과를 반환할 때 주의해야 한다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


input = sys.stdin.readline
N, M = map(int, input().split())
numbers: list[int] = list(map(int, input().split()))
dp: list[int] = [0]
for idx, number in enumerate(numbers):
    dp.append(dp[idx] + number)

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

다른 풀이

추가적으로 아래와 같이 내부 intertools 모듈 내에 있는 accumulate() 함수를 사용하여 더 쉽게 누적 합을 저장할 수 있다.

이때 accumulate() 내장 함수의 경우 첫 번째 매개변수로 이터러블(Iterable)한 객체를, 두 번째 매개변수로 연산의 종류를 -이때 기본값은 operator 모듈의 add() 함수- 마지막 매개변수로는 초기값 -이때 기본값은 None - 을 설정해줄 수 있다.

예를 들어 accumulate(iterable, function, inital) 와 같은 형태다.

import sys
from itertools import accumulate


input = sys.stdin.readline
N, M = map(int, input().split())
dp: list[int] = list(
    accumulate(list(map(int, input().split())), initial=0)
)
for _ in range(M):
    i, j = map(int, input().split())
    print(dp[j] - dp[i-1])