[예제] [파이썬] [탐색] [투 포인터] 2003번: 수들의 합 2

 

투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709

 

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

 

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을 넘지 않는 자연수이다.

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

▣ 입력예제 1
8 3
1 2 1 3 1 1 1 2

▣ 출력예제 1
5

 

---

 

예제1 설명 

8개 숫자가 주어짐 

1 2 1 3 1 1 1 2 

더해서 3이 되는 경우의 수를 출력해라

 

주어진 숫자가 어마어마하게 큼 -> 이분탐색

import sys
sys.stdin=open('input.txt','r')

def solution(N,M,arr):
    lt, rt = 0, 1               # 범위 0부터 1까지 더해봄, left, right
    add = arr[0]                # 첫번째 값 하나
    cnt = 0 
    while True:
        if add<M:                 # 목표값 미달 
            if rt<N:              # 범위 안에 있으면 
                add += arr[rt]    # rt까지 더해봄
                rt+=1             # rt를 오른쪽으로 더 이동시켜보자
            else:                 # 범위를 넘어 서면 
                break             # 멈춤
        elif add==M:              # 목표값 도달 
            cnt+=1                # 카운트 
            add-=arr[lt]          # 다음 거를 살펴보기 위해 현재 왼쪽 시작 수를 제거
            lt+=1                 # 다음 거를 살펴보기 위해 왼쪽 범위 이동
        else:                     # add > M, 더해준게 목표값을 넘어서면 
            add-=arr[lt]          # 다음 거를 살펴보기 위해 
            lt+=1                 # 오른쪽으로 이동 

    return cnt

if __name__=="__main__":
    N,M=map(int, input().split())
    arr=list(map(int, input().split()))
    print(solution(N,M,arr))

 

---