시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 191 | 53 | 41 | 28.472% |
0부터 N-1까지 모든 정수를 한 번씩 포함하고 있는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A를 이용해서 A와 길이가 같은 자식 배열 B을 아래와 같은 방법으로 구할 수 있다.
위의 과정을 통해서 만든 순열 A의 자식 배열 B가 순열인 경우에 순열 A를 완벽한 순열이라고 한다.
아래 표는 길이가 3인 모든 순열과 그 순열의 자식 배열을 나타낸다. {1, 2, 0}과 {2, 0, 1}은 자식 배열도 순열이기 때문에, 두 순열은 완벽한 순열이다.
A | B |
---|---|
0, 1, 2 | 0, 0, 0 |
0, 2, 1 | 0, 0, 0 |
1, 0, 2 | 0, 1, 0 |
1, 2, 0 | 0, 1, 2 |
2, 0, 1 | 0, 2, 1 |
2, 1, 0 | 0, 2, 0 |
길이가 N인 순열 P가 주어진다. 이때, P와 차이가 가장 작은 완벽한 순열 Q를 구하는 프로그램을 작성하시오. 두 순열 P와 Q의 차이는 P[i]와 Q[i]의 값이 다른 i의 개수이다.
첫째 줄에 순열 P의 크기 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄에는 순열 P가 주어진다.
첫째 줄에 입력으로 주어진 순열 P와 차이가 가장 작은 완벽한 순열 Q를 출력한다. 가능한 순열 Q가 여러 가지인 경우에는 자식 순열이 사전순으로 가장 앞서는 것을 출력한다.
6 4 0 5 2 1 3
2 0 5 4 1 3
3 2 0 1
2 0 1
8 2 7 3 0 6 4 5 1
1 7 3 0 6 2 5 4
13 11 8 10 1 5 4 0 7 3 9 12 6 2
1 8 10 2 5 7 0 9 3 11 12 6 4
6 0 1 4 2 3 5
1 2 4 5 3 0
8 0 2 6 5 7 3 1 4
1 2 6 5 7 4 3 0