[백준][C++] 19539: 사과나무

문제 링크: https://www.acmicpc.net/problem/19539

 

UCPC 2020 예선 H번입니다.

관찰이 좀 필요한 문제입니다. 예제가 적절히 있어서 푸는데 지장은 없습니다.

 

일단 나무별로 키를 2로 나눈 것의 몫(=d)과 나머지(=r)를 각각 더해서 구합니다.

이제 이걸로 어떻게 할 것인가..? 적당히 예를 들어봅시다

나무가 2 2 1 1 이렇게 있으면 d=2, r=2 깔끔하게 떨어집니다

나무가 2 2 1 1 1, 2 2 1 1 1 1, .. 이런식으로 1이 추가되면 1짜리 물뿌리개는 뿌릴 수 있어도 2짜리는 못뿌리니 안됩니다

그럼 2 2 2 일때를 생각해봅시다. d=3, r=0입니다. 2짜리 물뿌리개는 1, 2번나무에 뿌리고 1짜리 물뿌리개는 3번에만 뿌리면 되겠죠. 이러면 3번 나무를 1 1로 쪼갠다고 생각해봅시다. 그러면 d=2, r=2가 됩니다. 이때는 자명하죠

 

식을 세워보면 x를 2->1로 쪼갤 나무의 수라고 했을 때 d-x = r+2x, x=(d-r)/3이 됩니다.

이때 x는 0이상 정수여야 합니다. 0 이상 정수가 아니면 NO를 출력합니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<int> v(n);

	int d=0, r=0;
	for (auto& c : v) {
		cin >> c;
		d += c / 2;
		r += c % 2;
	}

	if ((d-r)%3==0 && d>=r)
		cout << "YES\n";
	else
		cout << "NO\n";
	
	return 0;
}