벡즌 19539 사과나무 c++

문제

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

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

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

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

입력

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

두 번째 줄에는 N$N$개의 정수 h1,h2,⋯,hN$h_1,h_2,\cdots,h_N$이 공백으로 구분되어 주어진다. (0≤hi≤10 000$ 0 \leq h_i \leq 10\ 000$) hi$h_i$는 갊자가 바라는 i$i$번째 나무의 높이이다.

출력

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

예제 입력 1 복사

1
0

예제 출력 1 복사

YES

예제 입력 2 복사

2
4 3

예제 출력 2 복사

NO

예제 입력 3 복사

3
10000 1000 100

예제 출력 3 복사

YES

예제 입력 4 복사

5
1 3 1 3 1

예제 출력 4 복사

NO

 

 

문제유형 - 그리디 알고리즘

 

이해가 안가서 다른 블로그를 참고해서 풀어도 div >= sum/3 이면 YES라는 식이 이해가 안갔다.

 

1. 입력을 받으면서 모든 원소값을 다 더한 sum을 받는다

2. 입력을 받으면서 각 원소값에 / 2 를 한 값을 div에 저장한다

3. 만약 sum %3 == 0이 아니면 1+2 = 3 으로 나눈게 0이 아니라면 즉  1,2를 골고루 사용하지 않은게 된다 따라서 NO를 출력한다

4. 만약 sum %3 == 0 이라면 1차 조건을 완료 한다 하지만 sum을 3으로 나눈 값 보다 모든 원소의 2로 나눈 값의 합이 적으면 NO를 출력한다 그 이유는 전체원소합을 3으로 나눈값은 즉 총 횟수랑 같다고 보면 된다 근데 이 총 횟수보다 2로 나눈값이 적다면 말이 안되게 된다

그래서 2로 나눈값들의 합이 3으로 나눈 값보다 적다면 NO를 출력하고 그게 아니라면 모두 YES를 출력해 준다.

 

#include <bits/stdc++.h>

using namespace std;
int n ;

vector<int>v;

int main(){

    cin >> n;

    int sum=0;
    int div=0;

    for (int i = 0; i <n ; ++i) {
        int a ;
        cin >> a;
        sum += a;
        div += a/2;

    }

    if(sum%3!=0){
        cout << "NO";
    }else{
        if(sum/3 <= div){
            cout << "YES";
        }else{
            cout << "NO";
        }
    }


}