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

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

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

투포인터 문제다.

 

풀이

짝수가 연속된 수열에서 k번의 삭제를 할 수 있다는 얘기는 최대 k개의 홀수가 담긴 배열의 크기를 찾는 것과 같은 이야기다. 구간의 범위를 나타내는 head와 tail 변수를 사용하여 탐색한다.

 

구간 안에 홀수가 k개 이하라면 tail을 증가시켜 구간을 늘린다. 매 탐색마다 구간의 크기는 (tail - head - 홀수의 개수)가 된다. 해당 부분의 최댓값을 출력하면 정답이다.

 

구간의 범위를 나타내는 head와 tail 변수를 사용하여 범위를 탐색, 구간 안에 홀수가 k개를 초과한다면, head를 증가시켜 구간을 축소시켜 홀수의 개수를 조절한다. tail이 이미 N이라면, 더 이상 증가시킬 수 없다는 뜻이므로 반복문 종료.

 

정답 코드

해당 문제는 같은 문제지만 수열의 크기 범위만 더 좁은 22857 문제에서도 정답을 받을 수 있다.