[백준/C++] 19539번 사과나무 풀이

---

처음에는 결국 모든 숫자를 만들 수 있으니 전체 합이 3의 배수인지만 확인하면 되는거 아닌가? 했다.

 1 1 1 3 3 이면 반례가 생기는 것을 알게 되었다..

 

3의 배수는 만들 수 있는 숫자니 일단 모든 숫자는 3으로 나눈 나머지로 바꾼 후 1의 갯수와 2의 갯수를 비교하면 되지 않나? 했다.

10 1 1이 반례가 되었다.

 

뭔가 2가 실마리가 되는 것 같은데 20분이 지나서 힌트를 참조했다. 괜히 참조한 것 같다. 조금만 더 고민해볼 걸

결국 3의 배수이면서 2의 갯수가 물뿌리는 토탈 횟수보다 많으면 된다.

 

reason

1. 전체 수의 합이 3의 배수이면 물뿌리개를 동시에 사용해서 며칠이 걸리는지 체크 가능하다.
   (즉 배수가 아니면 물뿌리개를 동시에 사용해서 만들 수 없는 숫자이다.)
2. 2만큼 성장하는 물뿌리개 사용 횟수가 전체 걸리는 날과 같다면 3의 배수므로 1도 2와 같은 횟수 사용했으니 무조건 충족
3. 2만큼 성장하는 물뿌리개 사용 횟수가 전체 걸리는 날보다 크다면 2 중에 몇은 1을 2번 사용하여 만들 수 있고 3의 배수이므로 충족

---

#include <bits/stdc++.h>
using namespace std;
int N, now, cnt_2, sum ;

int main()
{
    cin >> N ;
    for(int i = 0 ; i < N ; i++)
    {
        cin >> now ;
        sum += now ;
        cnt_2+= now / 2 ;
    }
    if(sum % 3 != 0) cout << "NO\n" ;
    else cnt_2 >= sum / 3 ? cout << "YES\n" : cout << "NO\n" ;
}

---

느낀점: 코드는 정말 간단한데 그리디는 무엇을 그리디하게 가져가는지 알아내는게 너무 어렵다. 언제쯤 깨우칠까...

어떻게 깨우칠 수 있을까 너무 벽이 느껴진다.

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

19539번: 사과나무