A[x]는 30,000을 넘지 않는 자연수라는 조건이 중요함
자연수이기 때문에 가능한 방법
i =a,j=b의 합이 M보다 작았고, i =a,j=b+1의 합이 M보다 큰 경우를 생각해보자
A[x]는 30,000을 넘지 않는 자연수이기에 한번 M보다 커진다면 다시는 작아질 수 없다.
그렇기에 j를 증가시키지 않고 i를 증가시킴
2번 방법에서 i =a,j=b이고 j=b+1 일 때 M보다 크다면 i =a+1,j=a+1부터 다시 시작했는데 그럴 필요가 없다.
j를 초기화 하지 않고 b+1로 그대로 유지해도 된다
i =a,j=b
i =a,j=b+1
i =a+1,j=b+1
why?
i =a+1이고, a≤j≤b인 경우에서 합이 M이 되는 경우는 있을 수가 없다.
이게 무슨 말이냐면
만약 A[a+1]+…+A[b] == M 라고 한다면 A[a]+A[a+1]+…+A[b] > M가 되어야한다. 즉, A[a]+A[a+1]+…+A[b]<M가 틀린 가정이 되므로 A[a+1]+…+A[b] == M는 절대 불가능하다.
그래서 j는 그대로 두고 i만 1증가시켜주면 된다.