백준 6198번 - 옥상 정원 꾸미기 (C++)

문제

 

구현 방법

높이 H를 입력 받을 때 마다, 이를 list에 저장한다.(Vector가 더 효율적일듯) 이후, list를 역순으로 순회하며 만약 순회중인 해당 값이 H보다 크다면, 정답 MAX에 list의 size를 더하고 순회를 중단합니다. 만약 H보다 작다면, 해당 값을 삭제시키고 순회를 마저 진행합니다. 이 과정을 반복하면 list에는 결국 내림차순으로 데이터가 저장되기 때문에, 한번이라도 H보다 값이 크다면 이후의 순회는 생략하는 구조입니다.

코드

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N;
    long long Max = 0;
    cin >> N;
    list<int> Height_List;
    for (int i = 0; i < N; ++i)
    {
        int H;
        cin >> H;
        if (i != 0)
        {
            for (list<int>::iterator iter = Height_List.end();;)
            {
                iter--;
                if (H >= *iter)
                    iter = Height_List.erase(iter);
                else
                {
                    Max += Height_List.size();
                    break;
                }
                if (iter == Height_List.begin())
                    break;
            }
        }
        
        Height_List.emplace_back(H);
    }
    cout << Max;
}