문제 풀이

부분합 + 이분탐색으로 풀 수 있다.

먼저 presum 배열에 i번째 까지의 홀수의 개수를 저장한다.
그리고 for문으로 n의 인덱스를 순회하면서 이분탐색을 수행한다.
이 이분탐색은 i번째 인덱스를 r로 두고 r과 가장 멀리떨어진 l 즉 최소 l값을 구하는 역할을 한다.
l이 점점 왼쪽으로 갈 수 있는 조건은 l과 r사이에 존재하는 홀수의 개수가 k개를 넘지 않아야한다. 그러므로 이분탐색으로 빠르게 최소의 l을 구한다.
그러면 앞에서 구해준 l을 통해서 l과 r까지의 길이에서 그 사이에 존재하는 홀수의 개수를 빼주면 짝수로 이루어진 연속한 부분수열을 구할 수 있다.
이 과정을 모든 n까지 모든 과정에서 수행해서 그 중 최대값을 찾으면 된다.

이 풀이는 O(nlogn)의 시간 복잡도를 가졌으며
가장 긴 짝수 연속한 부분 수열 (large) 문제와 같이 최대 n이 100만 최대 k가 10만이어도 해결이 가능하다.

문제 링크

boj/22857

소스코드

PS/22857.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 [] presum= new int [50001];
        static int []arr = new int [50001];
        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());
            }
            presum[0] = arr[0] %2 ==0? 0 :1;
            for(int i=1;i<n;i++)
            {
                if(arr[i]%2 ==0) {
                 presum[i] = presum[i-1];
                }
                else
                    presum[i] = presum[i-1] + 1;
            }
            int ans = 0;
            for(int i=0;i<n;i++)
            {
                int l = 0, r= i;
                while(l<=r)
                {
                    int mid = (l+r)/ 2;
                    int cnt;
                    if(mid ==0)
                        cnt = presum[i];
                    else
                        cnt = presum[i] -presum[mid-1];
                    if(cnt <= k)
                    {
                        r= mid - 1;
                    }
                    else
                        l= mid+1;
                }
                int left = r+1;
                if(left==0)
                    ans = Math.max(ans, i - left + 1 -presum[i]);
                else
                    ans = Math.max(ans, i-left + 1 -(presum[i]- presum[r]));
            }
            bw.write(Integer.toString(ans));
            bw.flush();

        }
    }