백준 19539 사과나무(C++)

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

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    int sum = 0;
    int cnt = 0;

    arr.resize(n);


    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
        cnt += arr[i] / 2;
    }

    if (sum % 3 == 0 && cnt >= sum / 3) {
        cout << "YES";
    } else {
        cout << "NO";
    }



    return 0;
}

1. 문제

n개의 목표 사과나무의 길이가 주어진다. 이를 한 번에 두 물뿌리개를 사용하여 만들려 한다. 하나는 사과나무를 1 만큼 성장시키고, 다른 하나는 사과나무를 2 만큼 성장시킨다. 한 번에 두 물뿌리개를 동시에 사용해야 하고, 같은 나무에 사용이 가능할 때, 해당 길이의 사과나무를 만들 수 있는 지 여부를 YES, NO로 출력하라.

2. 풀이

• 각각 1, 2씩 자라는 물뿌리개를 동시에 사용해야 하므로 나무의 총 합은 3의 배수여야 한다.
• 만약 2 만큼 성장시키는 물뿌리개의 사용 횟수가 물뿌리개 사용 날짜와 같다면 나머지는 1 만큼 성장시키는 물뿌리개로 채울 수 있다.
• 만약 2 만큼 성장시키는 물뿌리개의 사용 횟수가 물뿌리개 사용 날짜보다 크다면 2를 1을 두번 사용하는 것으로 쪼개어 만들 수 있다.

위 논리에 의해 전체 나무의 높이 합이 3의 배수이면서 2 만큼 성장시키는 물뿌리개의 사용 횟수가 물뿌리개 사용일 이상이어야 한다.

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
        cnt += arr[i] / 2;
    }

    if (sum % 3 == 0 && cnt >= sum / 3) {
        cout << "YES";
    } else {
        cout << "NO";
    }

 하루에 전체 나무의 높이가 총합 3씩 늘어나므로 물뿌리개 사용일은 sum/3이다. 이를 활용하여 계산하면 정답을 구할 수 있다.