[백준] 17608. 막대기 <C++>

Olympiad > 한국정보올림피아드 > KOI 2019 1차대회 > 초등부 1번

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

17608번: 막대기

어렵지 않았던 문제다. 

약간 입체적으로 생각해볼 문제?

 

 

막대기를 오른쪽에서 볼 때 각각의 막대기 앞에 자신보다 큰 것이 있다면 보이지 않는다.

 

오른쪽에서 시작하여 왼쪽으로 가며 큰 값을 기억하고, 만약 기억해둔 큰 값보다 자신이 크다면 막대기는 보인다.

 

큰 값을 기억하며 개수도 세주는 방법이다.

 

 

 

<배열만 이용>

#include <iostream>
using namespace std;

int main() {
  int arr[100001], n, max=0, count=0;

  cin>>n;

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

  for(int i=n-1; i>=0; i--)  //n-1번 방까지 입력된 배열을 거꾸로 읽어간다.
  {
    if(max < arr[i])  //뒤부터, 앞으로 읽어가면서 max변수에 가장 긴 막대기의 길이를 저장하고, 개수를 세준다.
    {
      count++;
      max=arr[i];
    }
  }

  cout<<count;

}

 

 

<스택 이용>

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

int main() {
  int max=0, n, m, cnt=0;
  stack<int> s;

  cin>>n;
  for(int i=0; i<n; i++)
  {
    cin>>m; 
    s.push(m);
  }
  while(s.size())
  {
    if(max<s.top())
    {
      max=s.top();
      cnt++;
    }
    s.pop();
  }  
  cout<<cnt;
}