[BOJ] 1806번: 부분합

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

각 시작점에 대해, 어디까지 더하면 합이 S를 넘는지 O(lgN)만에 구할 수 있으면 시간복잡도 O(NlgN)으로 문제 해결이 가능합니다.

이를 위해서 D[i] = num[1]+num[2]...+num[i]로 정의를 했고 D[i]는 increasing임이 보장되므로 이진탐색을 통해 각 st_idx에 대해 D[i] >= S + D[st_idx-1]을 만족하는 i를 O(lgN)으로 찾았습니다.

https://github.com/encrypted-def/BOJ/blob/master/1806.cpp