BOJ - 불안정한 수열 28323

 

해결방법

결국, 불안정한 수열 중 가장 큰 케이스를 구하면 되는 것인데, 인접한 두 수를 더해서 홀수가 나오려면, 홀수 + 짝수의 경우밖에 없다.

즉, 홀짝홀짝순으로 배치된 경우를 찾아서 그 길이를 재면 되는 것이다.

예를 들어 5짜리 배열에 3 1 4 1 5로 입력되었다면, 홀짝홀짝이 가장 긴 부분, 3 4 1 5를 골라서 4짜리 배열을 만들 수 있다.

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    int max = 1;
    int prev = A[0] % 2;

    for (int i = 1; i < N; i++)
    {
        if (A[i] % 2 != prev)
        {
            max++;
            prev = A[i] % 2;
        }
    }

    cout << max << endl;
    return 0;
}