[백준 11659] 구간 합 구하기 4

1. 링크

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

2. 문제 설명

시간 제한: 1초

메모리 제한: 256MB

1) 문제

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

2) 입력

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

3) 출력

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

4) 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

3. 코드

#003. 구간 합 구하기
#11659

#입력
N, M = map(int, input().split(" "))
nums = input().split(" ")
nums = list(map(int, nums))
intervals = []
for _ in range(M):
    i, j = map(int, input().split(" "))
    intervals.append([i, j])

#부분합 미리 구해두기
temp = 0
interval_sum = [0] #"n번째"의 경우 1부터 시작하므로, 인덱스 0번은 0으로 정의해야 함
for i in range(N):
    temp += nums[i]
    interval_sum.append(temp)

#해당하는 부분합 출력
for [i, j] in intervals:
    print(interval_sum[j] - interval_sum[i-1])

4. 설명

가장 먼저, 입력을 받고 그 값을 N, M에 넣어준다. 그런 다음 nums 리스트에 N개의 수를 넣어준다. 그리고 M개의 줄에 주어진 합을 구해야 하는 구간 i, j를 [i, j] 형태로 intervals 리스트에 추가한다.

 

다음으로, 주어진 nums 리스트를 이용해 interval_sum 리스트에 부분합을 구해준다. 이 때 구하는 부분합 배열은 기존 리스트 데이터를 미리 더해둔 배열이라고 볼 수 있다. 이를 통해 시간복잡도를 줄일 수 있다. 그러한 부분합을 interval_sum 시트에 추가해준다.

 

그 후 intervals에 저장된 i, j를 불러와 해당되는 구간 합을 출력한다. 구간합을 구하는 공식은 부분합 리스트에서 index j(j+1번째)까지 합한 값에서 인덱스 i-1(i번째)까지 합한 값을 빼면 인덱스 i부터 j+1까지의 (i번째부터 j번째 수) 구간합이 나온다.

 

5. 주의

문제 출력을 보면 i"번째" 부터 j"번째" 수까지 합을 출력한다고 되어있다. 그렇기 때문에 nums의 실질적인 값이 시작하는 인덱스는 0이 아닌 1이 되어야 한다...! 이 점을 간과해 인덱스가 -1이 되어 엉뚱한 값을 뱉는 등 여러 번 오류를 마주했다.