백준 11659번 구간 합 구하기4 문제풀이, 파이썬

백준 11659번 : 구간 합 구하기4 문제풀이 [파이썬] 

---

<문제>

 

11659번 문제의 내용은 아래와 같습니다. 

 

 

구간 합 구하기 4 

문제

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

입력

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

출력

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

제한

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

예제 입력 1 복사

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 복사

12
9
1

---

 

 

<작성한 코드>

 

#백준 11659번
import sys

N, M = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
prefix_sum = [0]*(N+1)

for i in range(1, N+1):
  prefix_sum[i] = prefix_sum[i-1] + nums[i-1]

for _ in range(M):
  i, j = map(int, sys.stdin.readline().split())
  print(prefix_sum[j]-prefix_sum[i-1])

---

 

 

<코드 풀이>

 

본 문제를 풀기 위해서 누적합(구간합) 알고리즘을 사용하였다. 

누적합 알고리즘에 대한 내용은 아래 포스팅 참고!

2023.04.13 - [백준 알고리즘/Python] - [알고리즘] 누적합 알고리즘 - 파이썬

[알고리즘] 누적합 알고리즘 - 파이썬

 

 

 

import sys

N, M = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

가장 먼저 위처럼 시간초과를 예방하기 위해 import sys를 사용해주었다. 

그리고 문제에서 요구하는 입력값을 받기 위해서 N, M이라는 변수를 선언했고, 

nums 라는 이름의 배열을 선언해주었다. 

 

 

prefix_sum = [0]*(N+1)

다음으로는 누적합 알고리즘을 사용하기 위해서 

prefix_sum 이라는 이름으로 배열을 선언하고, 원소 '0'을 N+1개 할당해주었다. 

 

 

for i in range(1, N+1):
  prefix_sum[i] = prefix_sum[i-1] + nums[i-1]

다음으로는 위에 선언해준 누적합 배열에 

반복문을 돌면서 각 구간의 구간합을 재할당해준다. 

예를 들어 문제에서처럼 주어진 배열의 입력값이 

nums = [5, 4, 3, 2, 1] 이라면

누적합 배열의 원소들은

prefix_sum = [0, 5, 9, 12, 14, 15] 가 된다. 

 

 

for _ in range(M):
  i, j = map(int, sys.stdin.readline().split())
  print(prefix_sum[j]-prefix_sum[i-1])

이제 문제에서 주어지는 구간대로 원하는 결과값을 위처럼 출력하기만하면 된다.