부분합

부분합.. DP와 비슷한 부분이 있다. memoization을 해서 사용한다는 점에서 닮았다.

 

기본개념은, 미리 각 값까지의 합을 구한다음 저장하고, 그 값을 이용한다는것이다.

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

11659번: 구간 합 구하기 4

 

문제를 보자. 

새로운 리스트를 만들고, 리스트의 원소값에, 해당 인덱스까지의 합을 담는다. 그리고 각 부분합을 구하기 위해서 빼주면되는데, 예를들어 2부터 5까지라 함은, sum(5)-sum(1)이 되겠다. 즉 5까지의 합 - 1까지의 합 = 2부터 5까지의 합!

 

시간측면에서 큰 이득을 보는 알고리즘이다