어부의 고기잡이

1. 문제

현재 위치에서 N미터 떨어진 곳까지 물고기가 얼마나 있는지 주어진다. 정확히 M마리의 물고리를 잡고자 할 때 그물은 딱 한번 내리고 딱 한번 올릴 수 있다. 이때 정확히 M마리를 잡을 수 있는 경우의 수를 구하라.

 

예를 들어 5 3 7 2 1의 물고리가 존재할 때, 10마리의 물고리를 잡을 수 있는 경우의 수는 위와 같이 2가지가 존재한다. 가장 밑의 경우 떨어져있으므로 불가능한다.

 

2. 입력

3. 출력

가능한 경우의 수를 출력한다.

4. 알고리즘 : 투포인터

그물을 내리는 위치, 그물을 올리는 위치를 가리키는 두개의 포인터를 이용해서 구할 수 있다.

 

왼쪽에서 시작하기 때문에 물고기가 너무 적다면 그물을 올리는 위치를 오른쪽으로 이동하고, 물고기가 너무 많다면 그물을 내리는 위치를 오른쪽으로 이동한다.

5. 소스코드

# 입력처리
n, m = map(int,input().split())
fish = list(map(int, input().split()))

left, right = 0, 0 # 투포인터
number_of_fish = 0 # 현재 잡은 물고기 양
cnt = 0 # 경우의 수

while left < n: # 그물 내리는 위치가 n보다 작은 동안
    if right < n and number_of_fish < m: # 현재 잡은 물고기 양이 목표보다 그물 올리는 위치를 이동
        number_of_fish += fish[right]
        right += 1
    else : # 너무 많다면 그물내리는 위치를 이동
        number_of_fish -= fish[left]
        left += 1
    if number_of_fish == m: # 정확히 잡았다면 경우의 수 + 1
        cnt += 1
print(cnt)