[백준/알고리즘] 19539번 사과나무 (실버 1)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 19539번

백준 19539번 문제

풀이 알고리즘 : 그리디 알고리즘, 수학

 

UCPC 2020 예선 H번 문제인 사과나무 문제입니다.

대회 당시에는 해결방법이 정말 안보여서 꽤 어려웠던 문제인데, 다시 풀어보니 어렵지 않은 문제입니다.

 

먼저 물을 1회 뿌릴 때 마다 나무의 성장을 1, 2를 각 1회씩 시킬 수 있습니다.

즉, 한번에 성장시킬 수 있는 총 높이는 3입니다.

그래서 목표한 모든 나무의 높이의 합이 3의 배수가 아니라면 항상 "NO" 입니다.

 

만약 높이의 합이 3의 배수라면, 다음과 같이 생각할 수 있습니다.

총 X번 물을 뿌렸으면, 1만큼 성장을 X번, 2만큼 성장을 X번 한 것입니다.

 

즉, 높이의 합이 3의 배수이면서, 2만큼 성장을 X번 시킬 수 있다면 "YES"입니다.

왜냐하면 2만큼 성장을 X번 시켰다는 것은, 나머지 높이들을 1만큼 성장을 X번 시키면 되기 때문입니다.

 

그래서 입력을 받을 때 마다 2로 나눈 몫 (즉 2로 성장시킬 수 있는 개수)을 카운트하고, 그 개수가 총 높이 / 3 이상이라면 "YES"이고, 나머지는 항상 "NO"입니다.

 

아래는 정답코드입니다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, c3, c2;
	cin >> n;
	c3 = c2 = 0;
	for(int i = 0; i < n; i++) {
		int num; cin >> num;
		c2 += num / 2;
		c3 += num;
	}

	if(c3 % 3 != 0) {
		cout << "NO\n";
	} else {
		c3 = c3 / 3;
		if(c2 >= c3) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}

	return 0;
}