[백준][파이썬]11659.구간합구하기4 - 구간합(접두사합)

아래의 문제는 '백준'의 알고리즘 문제 내용이며 코드는 직접 푼 내용입니다.

---

 

11659.구간합구하기4

문제 및 입출력 

입출력예시

 

---

나의시도 

구간합알고리즘 적용

접두사합 배열을 만들어서, 부분합을 미리 계산해 두는 것이다.

그러면 i번째부터 j번째 수까지 합은 그 부분합배열[j] - 부분합배열[i-1]이 된다.

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
data=list(map(int,input().split()))

#구간합 알고리즘 적용
sum_value=0 #부분합계산
prefix_sum=[0] #접두사합 배열

#접두사합 배열 계산
for i in data:
    sum_value+=i #부분합
    prefix_sum.append(sum_value) #부분합결과 미리 저장해둠
print(prefix_sum)

for _ in range(m):
    i,j=map(int,input().split())
    #i부터j까지 합
    print(prefix_sum[j]-prefix_sum[i-1])

 

풀이과정

예를 들어 data가 [5 4 3 2 1] 이라는 배열을 가지고 있다면 
부분합배열은 이렇다. p=[0, 5, 9, 12, 14, 15]

p[0]=0

p[1]=1번~1번

p[2]=1번쨰~2번째 까지 합 = 5+4

p[3]=1번쨰~3번째 까지 합 = 5+4+3

 

그래서 

2번째부터 5번째까지의 합을 구하시오 =1~5까지 합 - 1~1까지합 = p[5]-p[1] 
3번째부터 4번째까지의 합을 구하시오 =1~4까지 합 - 1~2까지합 = p[4]-p[2]  

i번째부터 j번째까지의 합을 구하시오 =1~j까지 합 - 1~i까지합 = p[j]-p[i-1]  

배운점

• i번쨰부터 j번쨰까지 부분합 관련문제는 
• 구간합(접두사합) 알고리즘

---

참고 

참고한 블로그 링크

https://velog.io/@sch804/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-1157%EB%B2%88-%EB%8B%A8%EC%96%B4-%EA%B3%B5%EB%B6%80