Informatica Online Judge

  사다리 게임 #1 [1426 / 0592]

Time Limit(Test case) : 5000 (ms)
Number of users who solved : 23   Total Tried : 150


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JKJeong 2016]

Background

사다리 게임에 대해서는 다들 잘 알고 있을 것이다.

이번에는 사다리 게임을 만들 때, 가로줄과 세로줄을 이용하여 세로줄의 양 끝을 1:1로 매칭 시키는 게임이다.

다음 그림과 같이 1, 2, 3 세 명이 사다리 게임을 하고, 최종적으로 3, 1, 2와 같이 매칭을 시키고자 한다면 다음과 같이 사다리를 구성해야 한다.



그리고 다음과 같이 2개의 가로줄을 연결하면 그림과 같이 매칭 시킬 수 있다.



하지만 가로줄을 연결하는 방법은 매우 다양하다.

이 문제의 목적은 n명의 사람이 사다리 게임을 하면서, 최종적으로 매칭시키고자 하는 결과가 주어질 때 사용해야 할 가로줄의 수를 최소화 하는 것이다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 사람의 수를 나타내는 정수 n이 주어진다.

두 번째 줄에 매칭시킬 순열이 공백으로 구분되어 주어진다.

[입력값의 정의역]
2 <= n <= 1,000

Output

완성하기 위해서 필요한 가로줄의 최솟값을 출력한다.

IO Example

입력
3
3 1 2

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]