※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25629번 문제인 홀짝 수열이다.
문제는 아래 링크를 확인하자.

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

 

25629번: 홀짝 수열

길이가 $N$인 수열의 $i(1 \le i \le N)$번째 원소를 정수 $a_i(1\le a_i \le 100)$라고 하자. 동훈이는 이 수열을 잘 정렬해서 홀짝 수열로 만들고 싶다. 어떤 수열이 홀짝 수열이 되려면 다음 조건을 만족해

www.acmicpc.net

홀수번째 항에 홀수, 짝수번째 항에 짝수를 배치하기만 한다면 홀수번째 항끼리, 짝수번째 항끼리 각각 오름차순으로 정렬하는 것으로 조건을 항상 만족시킬 수 있다는 점을 관찰하자.

 

위의 관찰로, 조건을 만족할 수열의 조건은 "홀수번째 항에 홀수, 짝수번째 항에 짝수를 배치할 수 있을 것"이 된다. 전체 항의 개수가 2k개라면 홀수와 짝수가 각각 k개, 2k+1개라면 홀수 k+1개와 짝수 k개가 있는지를 확인하는 것으로 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int odd = 0, even = 0;
	int N; cin >> N;
	while (N--) {
		int x; cin >> x;
		(x & 1) ? odd++ : even++;
	}
	if (odd == even || odd == even + 1) cout << 1;
	else cout << 0;
}
728x90

'BOJ' 카테고리의 다른 글

[BOJ 25784 // C++] Easy-to-Solve Expressions  (0) 2022.10.30
[BOJ 25238 // C++] 가희와 방어율 무시  (0) 2022.10.30
[BOJ 25893 // C++] Majestic 10  (0) 2022.10.30
[BOJ 25377 // C++] 빵  (1) 2022.10.30
[BOJ 24723 // C++] 녹색거탑  (0) 2022.10.30

+ Recent posts