백준 알고리즘 - 2003 - 수들의 합 2

---

코드

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

답은 맞지만 for 문이 2번 돌아서 시간 초과가 뜬다.

 

 

n, m = map(int, input().split())
arr = list(map(int, input().split()))
lt, rt, num = 0, 1, 0
sum = arr[0]
while(True):
    if sum<m:
        if rt<n:
            sum += arr[rt]
            rt += 1
        else: # rt가 더 오른쪽으로 갈 수 없을 때
            break
    elif sum==m:
        num += 1 # 개수 +
        sum -= arr[lt] # 왼쪽 값을 빼주고
        lt += 1 # 왼쪽 인덱스 + 1
    else: # sum>m
        sum -= arr[lt]
        lt += 1

print(num)

배열의 왼쪽 인덱스와 오른쪽 인덱스를 지정하고

왼쪽 인덱스의 수부터 시작하여 더한다.

 

합이 m 보다 작다면,

오른쪽 인덱스를 한칸씩 오른쪽으로 이동시켜 주면서 오른쪽 인덱스의 값도 더해준다.

이때 오른쪽 인덱스가 리스트의 길이인 n보다 크다면 더이상 오른쪽으로 이동할 수 없으므로 break 한다.

 

더해가다가 합이 m과 같다면,

경우의 수를 하나 더해주고

다음 경우의 수를 위해 왼쪽 인덱스의 값을 합에서 빼준 다음

왼쪽 인덱스를 더해준다.

 

합이 m보다 크다면,

다음 경우의 수를 위해 왼쪽 인덱스의 값을 합에서 빼준 다음

왼쪽 인덱스를 더해준다.