백준 17608 - 막대기(C++)

문제

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

17608번: 막대기

 

풀이

오른쪽에서 봤을 때, 몇 개의 막대기가 보이는지 맞추는 문제이다.

현재 가장 긴 막대기의 길이를 계속 업데이트해 가면서 막대기들을 하나하나 비교해 가면 된다.

stack을 이용하여 풀이할 수 있는 문제이다.

stack에는 가장 늦게 들어온 수가 맨 위에 존재하게 되므로 오른쪽부터 고려할 수 있게 된다.

스택의 맨 위에 있는 수가 가장 긴 막대기의 길이보다 길다면 결과값을 증가시킨다. 

코드

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    int tall=0;
    stack<int> s;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        s.push(a);
    }
    int res=0;
    while(s.size())
    {
        if(tall<s.top())
        {
            tall=s.top();
            res++;
        }
        s.pop();
    }
    cout<<res;
}