백준 2003 풀이<Python>

문제

---

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

 

출력

---

첫째 줄에 경우의 수를 출력한다.

 

 

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

2003번: 수들의 합 2

 

풀이

---

제일 먼저 브루트포스로 모든 경우를 시도해 볼 수 있지만, 그렇기엔 시간이 너무 많이 걸리기 때문에,

1. Left , Right 포인터를 설정해서 
2. 설정된 값이 Left <---> Right 까지 모두 더한 값보다 작으면, Right를 옮겨주고,
3. Left <---> Right 까지의 값이 설정된 값보다 크게 되면, Right 을 늘려주는 건 의미가 없으므로 Left를 늘려준다.
4. 이런식으로 끝까지 가게 되면, 더이상 Right 이 오른쪽 끝까지 가게 되는데, 이때 반복을 종료시킨다.

n,s = map(int,input().split())
a = list(map(int,input().split()))
# 처음은 LEFT, Right 모두 0으로 설정해준다.
left = right = 0
sum = a[0]
ans = 0
while left <= right and right < n:
	# 첫번째 경우 sum 이 설정된 값보다 작게되면, right +=1
    if sum < s:
        right += 1
        if right < n:
            sum += a[right]
    # sum 이 설정된 값과 같으면 ans+=1 그리고 right+=1
    elif sum == s:
        ans += 1
        right += 1
        if right < n:
            sum += a[right]
    # sum 이 설정된 값보다 작으면 left+=1
    elif sum > s:
        sum -= a[left]
        left += 1
        if left > right and left < n:
            right = left
            sum = a[left]
print(ans)