[백준 19539] 사과나무

문제 링크 => 19539번: 사과나무 (acmicpc.net)

19539번: 사과나무

---

그리디 알고리즘 문제이다.

 

1과 2를 동시에 사용하여 나열된 나무의 높이를 만들어 내도록 하는 문제이다.

 

이때 다음과 같은 예는 성립하지 않는다.

 

[1 1 2 2 2] => 마지막에 2만 남으므로 성립하지 않음

 

[1 1 1 2 2 2 2] => 이 또한 마지막에 2만 남으므로 성립하지 않음

 

즉, 합이 3의배수가 아닌 경우는 무조건 "NO" 이다.

 

그리고 합이 3의 배수일때의 예를 살펴보도록 한다.

 

[1 1 2 2] => 1, 2를 모두 사용하여 만들어낼 수 있으므로 성립함 (1, 2를 총 2번 사용하고 총 합이 6이다.)

 

[100, 1000, 10000] => 1, 2를 모두 사용하여 만들어낼 수 있으므로 성립함 (1, 2를 총 11100/3 번 사용하고 총 합이 11100 이다.)

 

[1, 3, 1, 3, 1] => 합이 3의 배수이지만 1, 2를 모두 사용하여 만들어낼 수 없으므로 성립하지 않음 (2를 총 2번 사용하고 나머지 1을 독립적으로 제거할 수 없음)

 

위의 규칙성을 보아하니 2를 사용한 총 횟수를 op 라 하고 총 합을 sum 이라고 했을때 op >= sum/3 일 경우 성립함을 알 수 있다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

map<int, int> m;

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

	int n, sum=0, op=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		sum += x;
		op += x / 2;
	}
	
	if (sum % 3 == 0) {
		if (op >= sum / 3) cout << "YES";
		else cout << "NO";
	}
	else {
		cout << "NO";
	}

	return 0;
}