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

문제

 

 

접근 방식

숫자를 k번만 삭제해서 짝수로만 이루어진 부분 수열 중

가장 긴 부분 수열의 길이를 구해야 한다.

 

첫 숫자부터 시작 포인트로 정하고 나머지 하나의 포인터를 사용해

다음 숫자들을 탐색해나가면 된다.

{1, 2, 3, 4, 5, 6, 7, 8}

 

예를 들어 위와 같은 수열이 주어졌고, 2번만 삭제할 수 있다면

짝수만 남겨야하니 홀수를 만날 때만 삭제해주고

다음에 홀수를 만났을 때 더이상 삭제할 기회가 남아있지 않다면

현재 까지 수열의 길이를 계산해주면 된다.

 

(현재 까지 수열의 길이 = 끝 포인터 - 시작 포인터 - 삭제한 홀수의 갯수)

// 남은 삭제 기회
// 숫자

1	1	0	0	x
1	2	3	4	5

2	1	1	0	0	x
2	3	4	5	6	7

1	1	0	0	x
3	4	5	6	7

2	1	1	0	0
4	5	6	7	8

 

순서를 살펴보면 위와 같다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];

		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int end = 0;
		int max = 0;
		int rm = 0;

		for (int start = 0; start < n; start++) {
			while (end < n) {
				if (arr[end] % 2 != 0) {
					if (rm == k) break;
					rm++;
				}

				end++;
			}

			max = Math.max(max, end - start - rm);

			if (arr[start] % 2 != 0 && rm <= k) rm--;
		}

		System.out.println(max);
	}
}