[백준][누적합] 14465. 소가 길을 건너간 이유 5

14465. 소가 길을 건너간 이유 5

 

• 내 풀이

누적합
- 고장난거 0 고장안난거 1로 생각하고 보다가 누적합인것 파악

• zero[i] : i번째까지의 0의 갯수
  • zero[i]-zero[i-k]
  • : n에서부터 k만큼의 범위를 확인 → 안에 0이 몇개 인지
  • 그 중에 최솟값이 고쳐야할 최소 갯수

n,k,b=map(int,input().split())
nums=[1]*(n+1)

for _ in range(b):
    x=int(input())
    nums[x]=0
    
zero=[0]*(n+1)
for i in range(1,n+1):
    if nums[i]==0:
        zero[i]=zero[i-1]+1
    else:
        zero[i]=zero[i-1]

answer=float('inf')
for i in range(n,k-1,-1):
    answer=min(answer, zero[i]-zero[i-k])

print(answer)