[백준 19539번] 사과나무 (C++)

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int sum = 0;
    int cnt2 = 0;

    for (int i = 0; i < n; i++) 
    {
        int h;
        cin >> h;
        sum += h; 
        cnt2 += h / 2; //다른 물뿌리개 가능 횟수
    }

    if (sum % 3 != 0 || cnt2 < sum / 3) cout << "NO";
    else cout << "YES";
    return 0;
}

 

기본적으로 나무 하나를 1만큼 성장시키거나, 2만큼 성장시키기에 한 번에 3만큼 성장시킨다는 것을 알 수 있다.

따라서 나무 높이의 합산이 3의 배수여야만 물뿌리개를 모두 알맞게 사용할 수가 있다.

 

하지만 3의 배수를 체크하는 것만으로는 부족하다.

아래의 예시의 경우 3의 배수이지만, 2만큼 성장시키는 물뿌리개의 사용이 불가능한 케이스이다.

1 1 1 3 3 3

 

따라서 추가적으로 2만큼 성장시키는 물뿌리개의 가능 회수 또한 체크하여야 한다.

이를 위해 입력받은 높이에 대해 2로 나누어 해당 물뿌리개 사용 가능 회수를 카운팅한다.

이렇게 구한 회수는 총 물 뿌리개 사용 회수라고 할 수 있는 sum/3의 값보다 작으면 균형이 맞지 않아 불가능한 케이스므로 NO를 출력한다.