[ 백준 17608 ] 막대기 (C++)

백준의 막대기(17608) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 막대기들을 오른쪽에서 보았을 때, 몇 개의 막대기가 보이는지 구해야 하는 문제이다.

 

먼저, 막대기들을 오른쪽에서 보면 어떤 현상이 일어나는지에 대해서 이야기를 해보자.

예를 들어서 높이가 [ 1 , 2 , 3 , 4 , 5 ] 인 막대기들을 오른쪽에서 본다고 가정해보자.

그럼, 가장 먼저 높이가 '5'인 막대기가 보이게 될 것이다. 그 다음 막대기들은 ?? 당연히 보이지 않게 될 것이다.

왜냐하면 높이가 '5'인 막대기에 가려져 버렸기 때문이다. 가려져서 보이지 않는다는 것은, 현재 보고있는 막대기보다 높이가 더 낮기 때문에 보이지 않는다는 것을 의미한다.

그럼, [ 5 , 5 , 5 , 5 , 5 ] 를 생각해보자. 이 또한, 가장 처음에 높이가 '5'인 막대기만 보이게 될 것이고 나머지 막대기들은 가려져서 보이지 않게 될 것이다.

그렇다면, [ 5 , 4 , 3 , 2 , 1 ] 을 한번 살펴보자. 이 경우에는 5개의 막대가 보이게 될 것이다.

가장 처음에는 높이가 '1'인 막대가, 그 이후에는 높이가 '2'인 막대기이기 때문에 즉, '1'보다 더 큰 막대기 이기 때문에 보이게 될 것이다. 그 이후의 과정은 진행해보지 않겠다.

 

결과적으로 이야기해보자면, "현재 보이는 막대 중, 가장 높이가 높은 막대기 보다 더 높은 막대기가 나오면 그 막대기는 보이게 된다" 라는 것을 알 수 있다.

[ 3 , 4 , 5 , 2 , 1 ] 에서 보면, 가장 처음에는 '1'이 보이게 될 것이고, 그 다음으로 보이는 막대기는 '2'가 될 것인데, '1'과 '2'를 비교했을 때 더 높은 막대기는 '2'가 될 것이다. 그 이후에 막대기는 '5'가 될 것인데, '2'와 '5'를 비교했을 때 더 높은 막대기는 '5'가 될 것이다.

즉 ! 여기까지 봤을 때, 높이가 가장 높은 막대기는 '5'가 된다. 그 이후에 '3'과 '4'는 현재 보고 있는 막대기들 중, 높이가 가장 높은 막대기인 '5'보다 더 작기 때문에 보이지 않는 것이다.

 

[ 소스코드 ]

#include <iostream>
 
#define MAX 100010
using namespace std;
 
int N;
int Arr[MAX];
 
void Input()
{
    cin >> N;
    for(int i = 0 ; i < N; i++) cin >> Arr[i];
}
 
void Solution()
{
    int Answer = 0;
    int Max_Height = Arr[N - 1];
    Answer++;
    for(int i = N - 2; i >= 0; i--)
    {
        if(Arr[i] > Max_Height)
        {
            Max_Height = Arr[i];
            Answer++;
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    Solve();
}