[백준] 22862번: 가장 긴 짝수 연속한 부분 수열 (large) - Python

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

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

1 2 3 4 5 6 7 8 수열중에서 홀수를 K개 삭제할 수 있다는 것이 포인트 

따라서 연속해서 등장하는 홀수의 개수를 기준으로 현재 연속된 짝수의 개수를 수열의 길이라고 볼 수 있다. 

수열에서 인덱스를 하나씩 증가시키면서 이를 수열의 맨 처음 부분인 start 라고 본다. 

그리고 현재 위치인 start에서 짝수의 수열 길이를 갱신해준다음, start 값이 하나 증가하기 이전에 현재 start값에 대한 처리를 아래와 같이 해준다. 

 # start 지점이 바뀌므로 하나씩 삭제해주어야 함 !
    if data[start] %2 == 1: 
        odd_count -= 1
    else:
        length -= 1

 

import sys 
input = sys.stdin.readline 
answer = 0 #최대 수열 길이 
n, k = map(int, input().split())
data = list(map(int, input().split()))

odd_count = 0 # 홀수개수 
length = 0 #수열의 길이
end = 0  
for start in range(n):
    # 지우려는 홀수개수는 K개까지 포함 1 2 3 4 5 6 중에서 3 5 지울때 246 세어주어야 하므로 
    while odd_count <= k and end < n:
        if data[end]%2 == 1: # G
            odd_count += 1 
        else:
            length += 1 
        end += 1
    
    answer = max(length, answer)
    
    # start 지점이 바뀌므로 하나씩 삭제해주어야 함 !
    if data[start] %2 == 1: 
        odd_count -= 1
    else:
        length -= 1 
        
print(answer)