Algorithm/two pointer
[BOJ] 2003번 수들의 합2 - 구간합, 투포인터
Yejin
2023. 9. 22. 13:33
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
방법 1 : 구간합
n, m = map(int, input().split())
list = list(map(int, input().split()))
# 합배열 만들기
total = 0
sum_list = [0]
for i in range(len(list)):
total += list[i]
sum_list.append(total)
# 구가합을 빼면서 m이랑 같은게 있는지 확인
count = 0
for i in range(len(sum_list)):
for j in range(i+1, len(sum_list)):
if sum_list[j] - sum_list[i] == m:
count += 1
print(count)
방법2: 구간합 + 투포인터
n, m = map(int, input().split())
list = list(map(int, input().split()))
left = 0
right = 1
count = 0
while (left <= right and right <= n):
total = sum(arr[left:right]) # 구간합 계산
if (total < m):
right += 1
elif (total > m):
left += 1
else:
count += 1
right += 1
print(count)