파이썬)수들의 합2

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

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

arr = list(map(int, input().split()))


start = 0
end = 1

cnt = 0


while start <= end and end <= n:
    number = sum(arr[start:end])
    if number == m:
        cnt += 1
        end += 1
    elif number > m:
        start += 1
    else:
        end += 1

print(cnt)

굉장히 기초적인 투포인터 알고리즘 문제같다.

 

start,end를 각각 0,1로 설정하고 그 arr이라는 리스트의 구간들의 합을 구해 m과 비교한다

만일 sum이 m보다 크다면, start를 +1 증가시킨다.

반대로 m이 더 크다면 end를 +1 증가시킨다.

예를들어 [3,4,5,2,1,6,4]라는 리스트가 있고 m은 6이라고 하자.

처음 start,end는 0,1 이므로 

arr[start:end]는 [3]이 된다.

m(6) > 3이므로 end를 +1 증가시킨다.

그럼 end는 2가 되고 arr[start:end]는 [3,4]가된다.

sum은 7이고 7 > m(6) 이므로 start + 1이된다.

즉 m이 더 크다면 숫자를 더하는 역할(end+1)이고 sum이 더 크다면 숫자를 줄여주는(start+1)이 된다.