PS/Python
[Python] 백준(BOJ) 2003번: 수들의 합2 - 투포인터 알고리즘
yoo.o
2020. 12. 11. 03:16
반응형
문제
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
풀이
투포인터 알고리즘을 이용해서 풀었다. 배열의 인덱스를 start, end 두 변수에 저장해서
원하는 합보다 sum(arr[start:end])가 작아질 경우엔 end를 하나 증가시키고, 같거나 클 경우엔 start를 하나 증가시킨다.
주의할점은 루프를 끝내는 시점이다. end가 배열의 길이가 되었을때 루프를 멈춰줬더니, start가 이동하면서 하나씩 빼주는 부분이 생략되어 틀린 답이 나왔다. 또 arr[start]가 범위 초과가 되지 않도록 while not (start == end == N)으로 설정해줬다.
import sys
N, S = map(int, sys.stdin.readline().split(" "))
arr = list(map(int, sys.stdin.readline().split(" ")))
start = 0
end = 1
count = 0
sum = arr[start]
if sum == S:
count += 1
while not (start == end == N):
if sum < S and end < N:
sum += arr[end]
end += 1
else:
sum -= arr[start]
start += 1
if sum == S:
count += 1
print(count)
반응형