[BOJ] 2003 수들의 합 2

문제 링크 https://www.acmicpc.net/problem/2003 모든 알고리즘 문제는 C++로 구현되어 있습니다. 이 문제는 모든 경우의 수를 생각하면서 풀면 O(N^2)의 시간 복잡도가 나오게 된다(시작지점 0~N, 도착지점 0~N까지 움직이면서 경우의 수를 푸는 경우). 문제의 제한 시간이 0.5초이고 N이 최대 10000까지 나올 수 있으므로 이렇게 구하면 시간 제한에 걸릴 수 있다. 좀 더 시간 복잡도가 작은 방법이 필요하다. 수열의 처음 값을 가지고 있는 변수 sum을 생각해보자. i를 1부터 N까지 증가시키면서 sum에 A[i]의 값을 더한다. 더한 값이 M과 동일하다면 경우의 수를 1 늘려주고, M보다 크다면 sum 값이 M보다 작아질 때까지 가장 마지막에 더한 값부터 차례대로 ..