문제
N개의 숫자를 여러 그룹으로 쪼개려고 한다.
단, 그룹은 무조건 그룹의 합이 짝수인 그룹이 먼저 배치되고,
그룹의 합이 홀수인 그룹이 그 다음 배치되어야 하며, 이러한 순서가 연속해야한다.
숫자가 아래와 같이 주어지는 경우를 예를 들어 설명해보자.
11 2 17 13 1 15 3
위의 경우 [ 2 ] [ 11 ][ 17 3 ] [ 15 ] [ 13 1 ] 와 같이 다섯 개의 그룹으로 나누어 배치 할 수 있다.
N개의 숫자가 주어질 때 나눌 수 있는 그룹 수의 최댓값을 출력하자.
입력
첫 번째 줄에 숫자의 개수 N이 입력된다 (2≤N≤1000).
두 번째 줄에 N개의 숫자가 공백을 기준으로 입력되며, 해당 숫자는 1에서 100 사이의 정수이다.
출력
N개의 숫자가 주어질 때 나눌 수 있는 그룹 수의 최댓값을 출력하시오.
예제1
입력
7
1 3 5 7 9 11 13
출력
3
예제2
입력
7
11 2 17 13 1 15 3
출력
5
출처
USACO 2021 January Bronze