백준 19539 - 사과나무

 

 

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 물뿌리개 2개로 1, 2만큼 나무를 성장시킬 때, 모든 나무를 원하는 높이로 키울 수 있는지 여부를 판단해야 한다.

 

우선, 간단하게 판단할 수 있는 것은 물뿌리개를 한 번 사용한다하면 1, 2만큼 나무를 성장시키기 때문에 총 3의 높이를 키울 수 있다.

즉, 모든 나무의 높이가 3의 배수가 아니라면 나무를 키울 수 없다.

또한, 전체 높이를 3으로 나눈 몫이 각 물뿌리개를 사용한 횟수이다.

 

그렇다면 2씩 성장시키는 물뿌리개를 사용하는 횟수를 구한다면 판단할 수 있다.

2씩 성장시키는 물뿌리개를 사용한 횟수는 각 나무의 높이를 2로 나눈 몫과 같다.

단, 2로만 나누면 1을 사용하여 2를 성장시키는 경우를 포함하기 때문에 실제로는 전체 / 3 보다 클 수 있다.

따라서, 작은지만 판단해도 충분하다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
int sum = 0, cnt;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N;

    int total = 0;
    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;

        sum += num;
        cnt += num / 2;
    }

    if (sum % 3 || cnt < sum / 3) 
    {
        cout << "NO";
    }
    else
    {
        cout << "YES";
    }

    return 0;
}

---