백준 20974(Even More Odd Photos)

www.acmicpc.net/problem/20974

20974번: Even More Odd Photos

N마리의 소가 있고, 소들 마다 숫자가 부여된다. 

 

이 소들을 그룹할건데 숫자의 합이 짝, 홀, 짝, 홀로 반복되게끔 하는 그룹의 최댓값을 구하는 문제

 

우선 처음에는 짝부터 시작되는 것이 아니라 홀로도 시작이 가능한 걸로 생각을 해서 케이스 분류가 까다롭겠구나 했는데 짝부터 시작해서 더 간단해진 느낌 지금 생각해보니 어차피 홀로도 시작해도 홀로 시작하는 케이스 하나만 추가하면 되긴 했을 것 같네

 

짝 + 짝 -> 짝

홀 + 홀 -> 짝

홀 + 짝 -> 홀 

 

이렇게 된다는 사실은 너무 당연 

 

그래서 그냥 수의 합이 아닌 홀수와 짝수가 몇개인지만 알면 된다. 

 

홀 짝 갯수를 세고나서, 생각을 해보면 

 

1. 짝수가 홀수보다 큰 경우 

 

이 경우는 짝 홀 짝 홀 짝 홀 짝 홀 이런식으로 형성된 그룹에서 남은 것들을 모두 마지막 그룹에 넣어도 상관없다. 

따라서 그냥 홀*2+1

 

짝 홀 짝 홀 짝 홀 | 짝 -> 여기에 몰아 넣으면 ㄱㅊ

 

2. 홀수가 짝 + 1보다 큰 경우 

 

홀수 - 짝수의 값을 check라고 해보자 

 

check%3 == 0 인 경우 

 

짝 홀 짝 홀 짝 홀 | 홀->3의배수 

 

남은 홀이 3의 배수라면 

 

check/3 당 

짝수 하나를 만들고 홀수 하나를 만들 수 있다. 

 

따라서 even*2 +(check/3) *2

 

check%3==1 인 경우 

 

짝 홀 짝 홀 짝 홀 | 홀 -> 1개 남음 

 

check/3당 짝수하나, 홀수 하나 만들 수 있는 건 위에서 체크했었으니, 

 

한개남은걸 어떻게 처리할지만 생각해보면 된다. 

 

그냥 마지막으로 나온 홀에 넣고, 그 짝을 다시 마지막으로 나온 짝에 넣는다. 

 

그러면 

 

짝 홀 짝 홀 짝 이되고, 

 

계산을 하면 된다. 

 

check%3==2 인 경우

 

짝 홀 짝 홀 짝 홀 | 홀 -> 2개 남음

 

그냥 홀 두개 합쳐서 짝으로 만들면 된다.

 

짝 홀 짝 홀 짝 홀 짝 | -> check/3 의 갯수만큼 홀 짝 홀 짝 반복 

 

 

 

#include<iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int even = 0, odd = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a % 2 == 0)even++;
		else odd++;
	}
	if (even > odd) {
		cout << odd * 2 + 1;
	}
	else if (odd > even + 1) {
		int check = odd - even;
		if (check % 3 == 0) {
			cout << even * 2 + (check / 3) * 2;
		}
		else if (check % 3 == 1) {
			cout << even * 2 + (check / 3) * 2 - 1;
		}
		else {
			cout << even * 2 + (check / 3) * 2 + 1;
		}
	}
	else {
		cout << odd + even;
	}
}