[백준 11659번] 구간 합 구하기4 (Python/파이썬)

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

11659번: 구간 합 구하기 4

 

물론 입력받는 숫자들을 리스트에 다 넣어서 구간을 다 더하는 방법도 있겠지만, 구간 합을 구하는 성질을 이용하면  효율적으로 문제를 해결할 수 있다.

고등학교 시절 수열을 배울 때 수열의 합(S)을 구하고 구간을 다루는 연습을 했었다. 비록 규칙이 있는 수들이 아닐지라도 구간을 다루는 방법은 똑같으므로 떠오른다면 문제푸는데 도움이 될 것이다.

 

그래서 사용할 방법은 구간 합 배열을 만들어서 해결하였다.

예를 들어 5개의 숫자 배열 a = [1, 5, 2, 3, 8]이 있다면 합 배열은 s = [1, 6, 8, 11, 19] 이다.

구간 a[1]~a[3]사이의 합(10)을 구하고자 한다면 구간 합 배열에서 s[3] - s[0] = 10 이 됨을 알 수 있다.

따라서 구간의 시작점과 끝점을 start, end라고 하면 s[end] - s[start-1]을 통해 일일이 더하지 않고도 구간 합을 빠르게 구할 수 있다.

 

 

본인이 작성한 코드는 다음과 같다.

 

import sys
n, m = map(int,sys.stdin.readline().split())
num = list(map(int,sys.stdin.readline().split()))
section_sum = []  ## 합 배열 선언

## 합 배열 만들기
for i in range(len(num)):
  if i == 0:
    section_sum.append(num[i])  ## num의 첫번째 숫자를 넣어준다
  else:
    section_sum.append(section_sum[-1]+num[i])  ## 합 배열의 마지막 항에 num을 더한 수를 넣어준다

## 합 배열의 차를 이용하여 구간 합 구하기
for _ in range(m):
  start, end = map(int, sys.stdin.readline().split())
  if start == 1:
    print(section_sum[end-1])
  else:
    print(section_sum[end-1] - section_sum[start-2])

 

if 문을 사용하여 첫번째 항에 대한 처리를 하였지만 변수따로 선언하여 if문을 없앨 수도 있다