[BOJ / 구현] 19539 사과나무

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

19539번: 사과나무

 

19539 사과나무

알고리즘 : 구현

스택을 이용하여 구현하였는데 결국 나무 1,2인 애들은 겹칠 수가 없어서 스택이 아니라 count[2]짜리 배열을 만들어서 썼어도 됐을거 같다. 정렬을 하여 구현하여야 오류인 해를 피해갈 수 있습니다.

 

 

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

#define MAX 100005

stack<int> stk;

int namu[MAX];
int sum = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> namu[i];

        sum += namu[i];
    }

    if (sum % 3 != 0)
        cout << "NO\n";
    else
    {
        sort(namu, namu + n);

        for (int i = 0; i < n; i++)
        {
            if (namu[i] == 0)
                continue;
            else if (namu[i] == 1)
            {
                if (!stk.empty() && stk.top() == 2)
                    stk.pop();
                else
                    stk.push(1);
            }
            else if (namu[i] == 2)
            {
                if (!stk.empty() && stk.top() == 1)
                    stk.pop();
                else
                    stk.push(2);
            }
            else if (namu[i] >= 3)
            {
                if (!stk.empty())
                {
                    int t = 3 - stk.top();

                    while (!stk.empty() && namu[i] >= t)
                    {
                        namu[i] -= t;
                        stk.pop();
                    }
                }

                if (namu[i] != 0 && namu[i] % 3 != 0)
                    stk.push(namu[i] % 3);
            }
        }

        if (stk.empty())
            cout << "YES\n";
        else
            cout << "NO\n";
    }


    return 0;
}

시간 : 12ms

 

태그 : #BOJ 사과나무 #백준 사과나무 #19539 사과나무 #ucpc 2020 사과나무