https://www.acmicpc.net/problem/2003
시간 0.5초, 메모리 128MB
input :
- N M(1 ≤ N ≤ 10,000)(1 ≤ M ≤ 300,000,000)
- A[i] (1 <= A[i] <= 30000)
output :
- 경우의 수를 출력
조건 :
- i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수
이것도 투 포인터를 이용하던지, 모든 합을 구하던지 하는 거구만...
import sys
n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
ans = 0
for i in range(0, len(data)):
total = 0
for j in range(i, len(data)):
total += data[j]
if total == m:
ans += 1
break
if total > m:
break
print(ans)
사실 먼저 생각나는건 언제나 이중 for문 써서 반복하는 것이기 때문에 위의 것은 Pypy로 제출해서 맞았다.
투 포인터의 경우
start를 0
end를 1로 두고
ans = 0 으로 지정 해둔 다음.
값을 저장할 temp에 start의 아이템을 더한다.
해야할 것들.
temp == m
ans += 1
temp에서 가장 앞의 값 start 값을 빼주고
start += 1을 해서 시작지점을 옮긴다.
temp < m
temp += arr[end]
end += 1
temp > m
temp -= arr[start]
start += 1
그리고 끝내려고 할 떄.
이 반복문은 start < n 이면 계속 돌아가는데.
end == n 에 도달 했는데 temp 가 m 보다 작다는 말은 start를 옮겨도 값이 커지지 않는다는 거기 때문에 break를 걸어줘야 한다.
