문제 풀이

이 문제 또한 가장 긴 짝수 연속한 부분 수열 (small)과 같이 부분합 + 이분탐색으로 풀 수 있다. 이번에는 좀 다르게 풀어볼 것이니 부분합 + 이분탐색의 풀이를 보고싶다면
가장 긴 짝수 연속한 부분 수열 (small) 풀이 포스팅을 확인하면 된다.

또 다른 풀이 방법으로는 투 포인터를 사용해서 풀 수 있다.
small 문제의 풀이 부분합 + 이분탐색과 비슷하게 l과 r을 이용해서 r을 최대한 늘리고 l을 최대한 줄여서 최대 길이를 구한다.

cnt라는 변수를 사용해서 현재 구간에서 홀수가 몇개인지 기록을 한다.

cnt가 k 이상일 때, 즉 삭제할 수 있는 횟수가 남아 있지 않을 때에는
만약 현재 r이 짝수라면 r을 좀더 늘려줘도 관계없다.
하지만 홀수라면 r을 더 늘릴 수 없다. 그러므로 l을 오른쪽으로 좀 이동시켜 줘야한다. l을 이동하면서 이동하기 전의 l이 홀수 였다면 홀수를 하나 제거한 것을 취소한 것이므로 cnt를 하나 빼준다.

cnt가 k 미만일 때, 즉 삭제할 수 있는 횟수가 남아 있을 때에는
r을 늘리기만하면 된다. 역시 r이 홀수라면 cnt를 세어준다.

그렇게 하면 l이상 r 미만의 구간의 홀수를 최대 k개 제거하면서 만들 수 있는 가장 긴 짝수 부분수열을 구할 수 있다.
그 길이는 r - l - cnt로 구간의 길이에서 제거한 홀수 수와 같다.

문제 링크

boj/22944

소스코드

PS/22944.java

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int []arr = new int [1000001];
	public static void main(String[] args) throws IOException {

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++)
		{
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int ans = 0;
		int l=0,r=0,cnt = 0;
		while(l<=r && r<n)
		{
			if(cnt >= k)
			{
				if(r< n && arr[r] % 2 ==0)
					r++;
				else if(r <n && arr[r] % 2 == 1)
				{
					if(arr[l] % 2 == 1)
						cnt--;
					l++;
				}

			}
			else if(r <n){
				if(arr[r] % 2 == 1)
					cnt++;
				r++;
			}
			ans = Math.max(r-l-cnt,ans);
		}
		bw.write(Integer.toString(ans));
		bw.flush();

	}
}