완벽한 순열까지의 최소 차이
시간 제한2초메모리 제한128 MB
주어진 순열을 하나의 N-사이클, 즉 완벽한 순열로 바꾸는 데 필요한 최소 변경 위치 수를 구하는 문제입니다.
문제
0부터 N-1까지의 모든 정수를 정확히 한 번씩 포함하는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A로부터 같은 길이의 자식 배열 B를 다음과 같이 만든다.
- B[0] = 0
- B[i] = A[B[i-1]] (1 <= i <= N-1)
이 과정으로 만든 자식 배열 B가 다시 0부터 N-1까지의 모든 정수를 정확히 한 번씩 포함하는 순열이면, A를 완벽한 순열이라고 한다.
다음 표는 길이가 3인 모든 순열 A와 그 자식 배열 B를 보여 준다. {1, 2, 0}과 {2, 0, 1}은 자식 배열도 순열이므로 완벽한 순열이다.
길이가 N인 순열 P가 주어진다. P와 차이가 가장 작은 완벽한 순열 Q를 찾아야 한다. 두 순열 P와 Q의 차이는 P[i]와 Q[i]가 서로 다른 인덱스 i의 개수이다.
입력
첫째 줄에 순열 P의 크기 N (1 <= N <= 50)이 주어진다. 둘째 줄에 0부터 N-1까지의 모든 정수를 한 번씩 포함하는 순열 P가 주어진다.
출력
첫째 줄에 입력으로 주어진 순열 P와 차이가 가장 작은 완벽한 순열 Q의 차이를 출력한다.