점프 (JUNGOL 8595)

https://jungol.co.kr/problem/8595?cursor=MjcsMCw4

---

아이디어

어떤 정점에 대해서 오른쪽 간선과 왼쪽 간선의 이동 횟수가 다르다는것은, 그 정점을 기준으로 유턴을 했다는 것입니다. 만약 왼쪽 간선에서 더 많이 이동하였다면 왼쪽에서 와서 왼쪽으로 간 것이고 오른쪽 간선에서 더 많이 이동하였다면 오른쪽에서 와서 오른쪽으로 간 것입니다. 또한 각 간선을 사용한 절대적인 수치를 통해 간선을 높낮이의 관점에서 바라보면 한곳에서 왼쪽으로 튕기면 어디서 멈추는지를 생각해볼 수 있습니다. 

---

소스코드

#include <stdio.h>
#include <stack>

int arr[202020]={0};
int Next[202020]={0};
bool visit[202020]={0};

int main()
{
	int N,i;

	std::stack <int> stk;

	scanf("%d",&N);
	for (i=1;i<=N-1;i++)
		scanf("%d",&arr[i]);

	for (i=2;i<=N-1;i++)
	{
		if (arr[i-1]<arr[i]) stk.push(i);
		else if (arr[i-1]>arr[i])
		{
			int temp=stk.top();
			stk.pop();
			Next[temp-1]=i;
		}
	}

	for (i=1;i<=N;i++)
	{
		if (!visit[i]) printf("%d ",i);

		if (Next[i])
		{
			visit[Next[i]]=true;
			printf("%d ",Next[i]);
		}
	}
}