[BOJ] 2003번: 수들의 합 2

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

만약 i, j에 대해 이중 for문을 돌면서 경우의 수를 찾으려고 한다면 O(N^3)의 시간이 소요될 것입니다. 그렇지만 D[i] = A[0] + A[1] + A[2] + ... + A[i-1]이라는 Dynamic table을 만들 경우 D[i]는 단조증가함이 보장되므로 i=1~N에 대해 D[j] = D[i]-M을 만족하는 j가 존재하는지 binary search로 찾으면 O(NlgN)으로 문제를 해결할 수 있습니다.

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