[BOJ] 19539 : 사과나무

문제 링크

19539번: 사과나무 (acmicpc.net)

19539번: 사과나무

난이도가 골드였어도 이상하지 않았을 문제.

풀이

 처음에는 직접 모든 나무에 물을 주면서 YES or NO를 판단했다. 나무의 높이를 저장한 후 나무의 높이를 2또는 1을 깎으면서 모두 0이 될 수 있는지를 체크하려 했다. 하지만 이렇게 하면 나무를 3만큼 키우는게 맞는지 2만큼 키우는게 맞는지 1만큼 키우는게 맞는지 판단하기가 애매했다.

1. 하루에 무조건 합쳐서 3의 높이를 키워야하기 때문에 모든 나무의 높이의 합이 3의 배수가 아니라면 무조건 "NO"를 출력한다.

2. 2만큼 키우는 물뿌리개를 i번 사용한다고 하면 1만큼 키우는 물뿌리개도 당연히 i번 사용해야한다. 나무의 높이가 입력으로 주어질 때, 그 높이를 2로 나누어서 2짜리 물뿌리개를 몇 번 뿌릴 수 있는지 센다.

2짜리 물뿌리개를 뿌리는 횟수가 (모든 나무 높이의 총 합) / 3 보다는 크거나 같아야 원하는 높이를 만들 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll, int>, int>, vector<pair<pair<ll, int>, int>>, greater<pair<pair<ll, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100000 + 5;
vector<int> height;
int N;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int sum = 0;
    int cnt_2 = 0;
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        sum += num;
        cnt_2 += (num / 2);
    }
    if (sum % 3) {
        cout << "NO\n";
    }
    else {
        if (cnt_2 >= sum / 3)
            cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}