[백준] 22557_ 가장 긴 짝수 연속한 부분 수열(small) (c++)

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

22857번: 가장 긴 짝수 연속한 부분 수열 (small)

 

[규칙]

1. 수열에서 K번 삭제 가능
2. 삭제 후 짝수로 이루어져 있는 연속한 부분 수열 
3. 연속한 부분 수열

 

[실패 원인]

1. 부분 수열에 대해 내가 잘 몰랐다. 
   • array = [1,2,3,4,5,6,7]
     • 연속된 부분 수열 : {1}, {2}, {3}, {4], {5} ,.... {1,2}, {2,3},.... {1,2,3,4},....

 

[풀이 설명]

• 최대한 포인터를 사용하지 않고 해 보았다. 
• 어차피 연속된 부분 수열이기 때문에, 짝수부터 시작해야 한다고 생각했다.
  1. 짝수 시작 점부터 짝수 개수를 센다.
  2. 홀수가 나오면 홀수 개수를 센다 (세고 있던 짝수 수는 초기화한다.)
  3. 배열에 짝수, 홀수 수를 각각 넣는다. 
• 홀수의 개수가 들어있는 배열을 이용한다.
  1. 홀수의 개수가 들어있는 배열 0번째부터 더해서 K가 넘을 때까지 반복한다.
     • 반복하면서 짝수의 개수를 더한다.

간단하게 적었지만, 설명이 제대로 안 된 것 같아 그림을 그려서 설명해보자면

위의 그림처럼 노란색 밑줄은 짝수, 초록색 밑줄은 홀수이다.

짝수와 홀수가 연속된 부분을 개수를 세어 각각 배열에 넣은 모습이다. 

 

문제에서 원소를 K번 삭제하기 때문에 odd의 수가 K번 보다 작어야 한다. 

• 예를 들면 k가 2라면
  • odd배열에서 2보다 작거나 같게 반복하면서
  • even배열을 더해준다.
  • 그렇게 되면 2 + 3으로 젤 긴 수열은 5가 된다. 

 

• 다른 예시를 들어보면

K = 5 일 때,

odd가 2와 3을 선택을 해야

젤 큰 길이를 가지는 4 + 6 +5가 된다. 

 

 

[코드]

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int N, K;
	int odd_row = 0;
	cin >> N >> K;
	vector<int> even(N+1), odd(N+1);
	
    //odd, even배열에 넣기
	for (int i = 0,num, even_start =0,even_row = 0; i < N; i++) {
		cin >> num;
		if (even_start == 0 && num % 2 == 0)even_start = 1;
		if (even_start == 1) {
			if (num % 2 == 0) {
				even[even_row] += 1;
				if(odd[odd_row] > 0)odd_row++;
			}
			else {
				odd[odd_row] += 1;
				if (even[even_row] > 0)even_row++;
			}
		}
	}
    
    //최댓값 구하기
	int max_sum = 0;
	for (int i = 0, sum; i <= odd_row; i++) {
		sum = 0;
		for (int j = i, count = 0;  j <= odd_row; j++) {
			count += odd[j];
			if (count <= K)	sum += even[j];
			else { 
				sum += even[j]; 
				break; 
			}
		}
		max_sum = max(max_sum, sum);
	}
	cout << max_sum;
	return 0;
}