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

19539번 : 사과나무

---

문제)

이하는 최근 사과나무 씨앗을 구매하여 농장 뒷뜰에 일렬로 1번부터 N번까지 심었다. 이 나무들의 초기 높이는 모두 0$0$이다.

사과나무를 무럭무럭 키우기 위해 이하는 물뿌리개 2개를 준비했다. 한 물뿌리개는 나무 하나를 1만큼 성장시키고, 다른 물뿌리개는 나무 하나를 2만큼 성장시킨다. 이 물뿌리개들은 동시에 사용해야 하며, 물뿌리개를 나무가 없는 토양에 사용할 수는 없다. 두 물뿌리개를 한 나무에 사용하여 3만큼 키울 수도 있다.

물뿌리개 관리 시스템을 전부 프로그래밍한 이하는 이제 사과나무를 키워보려고 했다. 그 순간, 갊자가 놀러와서 각 사과나무의 높이가 이런 배치가 되었으면 좋겠다고 말했다. 이제 이하는 약간 걱정이 되기 시작했는데, 갊자가 알려준 사과나무의 배치를 이 프로그램 상으로 만들어내지 못할 수도 있기 때문이다.

이하는 이제 프로그램을 다시 수정하느라 바쁘기 때문에, 두 물뿌리개를 이용해 갊자가 알려준 사과나무의 배치를 만들 수 있는지의 여부를 판단하는 과정은 여러분의 몫이 되었다.

 

 

 

입력 :

첫 번째 줄에는 자연수 N이 주어진다. (1≤N≤100,000) 이는 이하가 뒷뜰에 심은 사과나무의 개수를 뜻한다.

두 번째 줄에는 N개의 정수 ℎ1,ℎ2,⋯,ℎh이 공백으로 구분되어 주어진다. (0≤ℎ≤10,000) ℎi는 갊자가 바라는 i번째 나무의 높이이다.

 

 

 

출력 :

첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다.

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, h;
int total;
int even;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        total += temp;
        if (temp > 1)
        {
            // 2 물뿌리개를 뿌릴 수 있는 횟수
            even += temp / 2;
        }
    }
 
    // 전체의 합이 3으로 나눠지지 않는다면
    // 무조건 만들 수 없음.
    if (total % 3)
    {
        cout << "NO";
    }
    else
    {
        // 2물뿌리개를 뿌릴 수 있는 전체 횟수가
        // 전체 횟수보다 많아야 한다.
        if (even >= total / 3)
        {
            cout << "YES";
        }
        // 그렇지 않으면 1이 더 많아지므로
        // 뿌릴 수 없음
        else
        {
            cout << "NO";
        }
    }
 
    // 1 3 1 3 1 의 경우
    // 2물뿌리개를 뿌릴 수 있는 횟수는 2번.
    // 전체 횟수는 3번이다.
 
    // 따라서 2물뿌리개를 뿌리고 나면 
    // 나머지는 1이 남게 되므로 NO가 된다.
 
 
 
    return 0;
}
 

 

 

---

출처 : https://www.acmicpc.net/problem/19539 

19539번: 사과나무