[백준 17608] 막대기

난이도

브론즈 II

📜문제

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

🔎접근

• 막대기를 쌓고 오른쪽에서 볼 때 보이는 개수
• 이런 유형의 문제는 주로 Stack을 이용한다.

🌞풀이

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> s;

	int num = 0;
	cin >> num;

	int height = 0;
	for (int i = 0; i < num; i++)
	{
		cin >> height;

		if (s.empty()) s.push(height);
		else
		{
			while (!s.empty() && s.top() <= height) // top이 입력수보다 작거나 같으면 다 pop 시키고 마지막에 push
			{
				s.pop();
			}
			s.push(height);
		}
	}
	cout << s.size() << "\n"; // 스택 사이즈 출력
	return 0;
}

• stack에 push하면서 top보다 큰 값이 입력되면 pop하고 push한다.

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기