[Algorithm] 수들의 합

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의
합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

<내 답안>

n, m = map(int, input().split())
list1 = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for j in range(i, n):
        sum = 0
        for k in range(i, j+1):
            sum += list1[k]
        if sum == m:
            cnt += 1
            break
print(cnt)

내가 푼 방식은 i와 j를 중첩 반복 시키면서 기준값을 정하고, 그 안에서 i~j 사이를 더하는 반복문을 또 넣는 것이였다. 그리고 만약 sum과 m 이 같아지면 cnt를 증가시키고 break를 해서 다시 i 반복문으로 올라오게끔 했다.
내 코드의 문제는 시간 초과였다. 시간 복잡도를 더 효율적이게 작성할 수 있는 것 같은데 내 머리로는 이 방법 밖엔..

<모범답안>

n, m = map(int, input().split())
a = list(map(int, input().split()))
lt = 0
rt = 1
tot = a[0]
cnt = 0
while True:
    if tot<m:
        if rt<n:
            tot+=a[rt]
            rt+=1
        else:
            break
    elif tot==m:
        cnt+=1
        tot-=a[lt]
        lt+=1
    else:
        tot-=a[lt]
        lt+=1

print(cnt)

해설은 반복문 한 번으로 풀었다. 내 코드가 얼마나 비효율적이게 푼 것이였는지.. 아무튼 while문 안에서 조건을 3개로 나누었다.
tot<m , tot==m, tot>m 으로 나누어 tot<m 이면 rt가 증가하고, tot==m 와 tot<m 이면 lt를 증가하는 방식이다.
처음에는 조건문 tot<m 안에 있는 if-else 조건문에서 else 일 때 왜 break가 되는지 정확히 이해되지 않았지만, 해설을 들으며 생각해보니 tot<m 일 땐 rt가 증가해야 하는데 더이상 증가할 수 없으므로 이 이후로부터는 무조건 m보다 작은 값들이기 때문에 break를 걸고 나오는 것이였다.

도대체 이런 생각은 어떻게 하는건가.. 다들 대다나다..