[백준][누적합][투포인터] 2003. 수들의 합 2

2003. 수들의 합 2

 

 

 

• 내 풀이
  • 시간복잡도 O(N^2) 가능 
  • 단순 for문 사용

n, m = map(int, input().split())
lst = list(map(int, input().split()))

for i in range(1, n):
    lst[i] += lst[i-1]

result = 0
for i in range(n):
    for j in range(i):
        if lst[i]-lst[j] == m:
            result += 1
    if lst[i] == m:
        result += 1

print(result)

 

 

• 다른 사람 풀이
  • 투포인터 사용
  • 값이 작으면 더 더해야 하므로 r+1
  • 값이 크면 하나씩 빼면서 체크해보기 위해 l+1

n, m = map(int, input().split())
lst = list(map(int, input().split()))

l, r = 0, 1
result = 0
while l <= r and r <= n:
    prefix_sum = sum(lst[l:r])

    if prefix_sum < m:
        r += 1
    elif prefix_sum == m:
        result += 1
        r += 1
    else:
        l += 1

print(result)