[백준] 17608 - 막대기

문제 링크

17608번: 막대기 (acmicpc.net)

17608번: 막대기

 

코드

#include <iostream>
#include <stack>

int main()
{
	int n;
	int sticks[100001] = {};
	std::stack<int> s({ 0 });

	std::cin >> n;

	
	for (int i = 0; i < n; i++)
	{
		std::cin >> sticks[i];
	}

	for (int i = n - 1; i >= 0; i--)
	{
		if (sticks[i] > s.top())
			s.push(sticks[i]);
	}

	std::cout << s.size() - 1;
}

 

 

풀이 해설

이 문제에 핵심은 이전에 등장 했던 사람보다 키가 같거나 작은 사람을 볼 수 없다.

즉 다르게 말하면 이전에 나왔던 사람들 보다 키가 커야한다

으로 재정의를 할 수 있다.

 

문제는 입력에서 주워진 값은 

왼쪽에서 오른쪽순서로 값을 주워지고 이 문제에서 요구하는 시야는 오른쪽에서 왼쪽이다.

그러면 왼쪽에서 오른쪽순서로 값을 받은 뒤 역순으로 읽으면 된다.

 

그러면 이 전재를 기반으로 코드를 작성하면 위와 같은 코드를 작성하게 되었다.

스택을 초기화하는 코드를 보면

	std::stack<int> s({ 0 });

으로 되어있다.

현재 문제에서는 모든 사람에 키가 1보다 크다.

그러면 이 스택에서 의미하는 0은 아직 사람을 세지 않은 경우이다.

0 말고도 스택을 비워서

		if (s.empty() || sticks[i] > s.top())

이렇게도 가능하다.