Problemas
어느 저녁 열심히 공부하던 정올 학생들은 너무 배가 고픈 나머지 야식을 먹기로 생각하였다. 정올 학생들은 몰아서 야식을 위해 돈 낼 사람을 가리기 위한 사다리 게임이 시작되려고 한다! 여기서 걸린 사람이 군말 없이 야식을 살 때 돈을 내야한다.
최근 매번 내기를 할 때 마다 졌던 태현이는 야식을 쏘게 되면 왠지 억울할 것 같아 이번 사다리 게임에서 내기 하는 사람들 중에서 가장 나이가 많은 것을 내세워서 사다리의 가로 줄들을 모두 긋고자 한다. 절대로 걸리기 싫은 태현이는 결과를 미리 정해놓고, 이에 맞게 결과가 결정되도록 하고자 한다. 하지만 재촉하는 친구들 때문에 최대한 빨리 그어야 하므로, 선긋기 횟수를 최소로 하려 한다.
가로 선은 인접한 세로 선 사이에만 그을 수 있으며, 다른 가로선과 만나서는 안 되며, 인접한 세로선들을 잇기 위한 가로선 사이에 다른 세로선이 존재해서는 안 된다.
결과를 만족시키기 위해 태현이가 그어야 하는 최소의 선의 횟수를 구하는 프로그램을 출력하라.
Entrada
입력의 첫 째 줄에는 사람의 수 N(1≤N≤100)이 입력되며, 다음줄에는 N개의 정수가 입력된다.
각 숫자는 사람의 번호를 뜻하며, 태현이가 원하는 결과를 뜻한다. 만약 "1 4 2 3"이면 첫번째 결과에는 1번이, 2번째 결과에는 4번이, 3번째 결과에는 2번이, 마지막에는 3번이 당첨되어야 한다는 것이다. 사람의 번호가 겹치는 경우는 존재하지 않으며, 1이상 N이하의 번호가 한번씩 입력된다.
Salida
입력에 대해 그어야 하는 최소 사다리의 수를 출력한다.
Ejemplo
4
2 1 4 3
2
Fuente
AJOU
Debes iniciar sesión para escribir código.