실버 IV음이 아닌 정수로 이루어진 길이 \(N\)의 배열 \(A\) = [\(A_{1}\), \(A_{2}\), \(\cdots\) , \(A_{N}\)]가 있다. 배열 \(A\)에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다. 이 때, 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 하는 시행의 최소 횟수를 구하여라. 단, 0 또한 짝수로 간주함에 유의하라.
예를 들어, 아래 그림과 같이 \(A\) = [4, 5, 1, 0]인 상황을 살펴보자. 이 경우, 마지막 두 원소를 교환하는 시행 과 가운데 두 원소를 교환하는 시행을 차례로 수행하면 \(A\)가 [4, 0, 5, 1]이 되어 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 할 수 있다.
- \(1 \le N \le 1\,000\,000\)
- \(0 \le A_i \le 2 \times 10^9\) (\(1 \le i \le N\))
- \(A_i\)는 정수이다.
첫 번째 줄에 정수 \(N\)이 주어진다.
두 번째 줄에 배열의 원소 \(A_{1}\), \(A_{2}\), \(\cdots\) , \(A_{N}\)이 사이에 공백을 두고 주어진다.
첫 번째 줄에 답을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(N \le 3\). |
2 | 40점 | \(N \le 1\,000\). |
3 | 50점 | 추가 제약 조건 없음. |
1
1
0
4
4 5 1 0
2
4
1 2 3 1
1
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 1차 대회 > 중등부 1번 / 고등부 1번