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

문제

길이가 𝑁인 수열 𝑆가 있다. 수열 𝑆는 1 이상인 정수로 이루어져 있다.

수열 𝑆에서 원하는 위치에 있는 수를 골라 최대 𝐾번 삭제를 할 수 있다.

수열 𝑆에서 최대 𝐾번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 𝑆의 길이 𝑁와 삭제할 수 있는 최대 횟수인 𝐾가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 𝑆를 구성하고 있는 𝑁개의 수가 공백으로 구분되어 주어진다.

출력

수열 𝑆에서 최대 𝐾번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

---

풀이

최대 K개의 홀수를 포함한 구간에서 짝수로만 이루어진 부분수열의 가장 긴 길이를 구하면 되는 문제다.

최대 K개의 홀수만큼 세어주자. 구간에 포함된 홀수의 수( cnt )가 K개와 일치한다면 더 이상 구간을 늘릴 수 없다. 

홀수든 짝수든 구간을 늘려주자( ++end)

오른쪽 구간을 최대로 늘렸다면, 현재 구간에 포함된 부분수열의 가장 긴 길이를 갱신하자.

왼쪽 구간이 갱신(증가)하며 경계에 위치한 요소가 홀수였다면 제외시켜 주자. 왼쪽에서 제외된 수 만큼 오른쪽에서 홀수를 다시 포함해야 탐색이 진행되기 때문이다.  

---

소스코드

보기

---

출처

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