[BOJ/C++] 25556 포스택

그리디 알고리즘을 이용해 문제를 해결할 수 있습니다.

처음에는 단순하게 스택 4개를 이용해서 문제를 풀어보려고 했으나 굳이 스택을 4개 안써도 될 것 같아서 다르게 접근해봤습니다.

스택 4개를 대체할 4칸짜리 배열을 만들고 각각의 인덱스가 스택의 역할을 대신하게 됩니다.

오름차순으로 만들기 위해선 스택에 들어오는 값은 기존의 값보다 커야합니다.

스택의 값과 비교하여 더 크다면 스택에 삽입하고 작다면 count를 증가시켜 4개의 스택에 모두 들어갈 수 없다면 오름차순으로 만들 수 없습니다.

#include <iostream>
#include<vector>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> v(4, 0);


    for(int i=0; i<N; i++)
    {
        int count = 0;
        int temp;
        cin >> temp;

        for(int& j : v)
        {
            if (temp > j)
            {
                j = temp;
                break;
            }
        	count++;
        }

        if (count >= 4)
        {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";

    return 0;
}