[백준 22862] 가장 긴 짝수 연속한 부분 수열(Large)

아이디어

• 시간초과를 피하기 위해 투포인터로 푼다.
• 해당문제의 경우 결국 가장 긴 짝수의 연속한 부분수열을 만들려면 짝수와 인접한 홀수를 제거해야 한다. 브루트 포스로 문제를 풀 경우 인접하지 않는 경우도 모두 고려하기 때문에 투포인터로 푸는 방법을 고려하였다.
• 처음 홀수의 갯수가 k개랑 같을 경우에 짝수의 길이를 갱신하는 것을 고려하였으나 그렇게 되면 만약 제거한 홀수 뒤에 짝수가 나오는 경우 길이에 오차가 생기기 때문에 k+1일 때 최대길이를 갱신한다.
• k+1개가 될때까지 end를 1씩 이동시키고 k+1개가 되면 start를 1씩 이동시킨다. end를 이동시키면서 홀수의 갯수와 짝수의 갯수를 각각 세주고 start를 이동시킬 때는 start가 짝수일 경우 짝수를 1 빼주고 홀수일 경우 홀수를 1 빼준다.예외처리
• 홀수의 갯수가 k+1 보다 작은상태에서 end가 끝에 도달해서 반복문이 끝나는 경우가 있다. 이 경우에 최댓값일 경우 최댓값 갱신을 해주지 못하고 끝나는 경우가 있음으로 반복문이 끝난 뒤에 꼭 result를 even과 비교해서 다시 갱신해주어야 한다.

n,k = map(int, input().split())
a = list(map(int, input().split()))

s,e = 0,0 # 시작, 끝
result = 0 # 짝수로 이루어져 있는 연속한 부분 수열중 가장 긴길이
even= 0 # s,e사이의 짝수 갯수
odd = 0 # 지우려는 홀수 갯수

while s < n and e < n:
    if odd > k:
        result = max(result, even)
        if a[s] % 2 == 1:
            odd -= 1
        else:
            even -= 1
        s += 1
    else:
        if a[e] % 2 == 1:
            odd += 1
        else:
            even += 1
        e += 1

# even을 계속 더해주다가 k+1개가 되지 못하고 반복문이 끝나는 경우가 있어 다시 한번더 갱신해준다.
result = max(result, even)
print(result)