Boj 19539) 사과나무

문제

백준 19539

설명

처음에 물을 주는 조합을 구해서 가능한지 판단하려고 했는데 힘들었다.

1 2
1 4 1
2 2 2

3 으로 다 지우면 위의 조합으로 모든 물주는 방법을 구할 수 있다. 문제는 7, 1, 1 같은 경우 4, 1, 1 로 바꿀 수 있는걸 보면 경우의 수를 셈하기가 까다롭다.

그러다 깨달은 것이 먼저 두 개짜리 물뿌리개로 최대한 물을 준다. 그리고 두 물뿌리개의 갯수가 맞도록 두 개짜리 물을 준 것을 취소하고 한 개짜리 물을 두 번 주는 것으로 바꾼다. 증명하긴 어려워도 이러면 될 것 같지 않은가?

물을 주는 것에 성공했을 때의 물주는 갯수를 a 라고 하고, 나무의 총 길이를 \(\text{Total}\), 2개짜리 물만 최대한 줄 수 있는 횟수를 \(\text{MaxTwo}\) 라고 하면 다음이 성립한다.

\[\begin{multline} 2*a + a = \text{Total} , \quad \text{MaxTwo} - k = a ,\ (0 \leq k \leq \text{MaxTwo}) \\ \shoveleft \text{MaxTwo} - \text{Total}/3 = k \\ \shoveleft 0 \leq \text{MaxTwo} - \text{Total}/3 \leq \text{MaxTwo} \end{multline}\]

이에 따라 두 조건을 검사하면 된다.

시간 복잡도

O(\(\mathrm{N}\))

코드

int main()
{
	fastio;

	int n; cin >> n;
	int total = 0, div2 = 0;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		total += a;
		div2 += a / 2;
	}
	cout << (total % 3 == 0 && div2 - total/3 >= 0 ? "YES" : "NO");
}