4800번 - 대충 정렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 30 | 16 | 15 | 57.692% |
문제
많은 프로그래밍 언어는 라이브러리 함수를 이용해서 배열의 값을 정렬할 수 있다. 이 함수를 사용해서 정렬을 하려면, less(x,y)와 같은 비교 함수를 작성해야 한다.
less(x,y)는 정렬한 순서에서 x가 y의 앞에 온다면 true를 리턴하는 함수이다. 이러한 함수는 항상 이치에 맞아야 한다. 즉, 서로 다른 두 원소 x와 y에 대해서, less(x,y)와 less(y,x)중 하나만 true가 되어야 한다.
이 문제에서는 수열에서 도치가 발생하지 않은 경우에 정렬되었다고 한다. less(x,y)에 대한 도치란, 크기가 n인 배열 A에서 less(A[j], A[i]) = true (0 ≤ i < j < n)를 만족하는 경우이다. (less(A[i], A[j]) = false와 동등한 의미가 아니다)
안타깝게도 어떤 프로그래머는 이런 비교 함수를 신중하게 작성하지 않는다. 이러한 경우에는 절대로 수열을 정렬할 수 없는 경우가 생길수도 있다.
less함수의 결과가 모두 주어진다. 이때, 이 함수를 이용해서 정렬했을 때, 도치의 개수를 최소가 되는 순열을 구하는 프로그램을 작성하시오.
입력
각 테스트 케이스의 첫째 줄에는 배열의 크기 n이 주어진다. (1 ≤ n ≤ 18) 배열의 각 원소는 0번부터 n-1번까지 번호가 매겨져 있다. 다음 n개의 줄에는 길이가 n인 이진 문자열이 주어지며, i번째 줄의 j번째 숫자는 less(i,j)의 리턴값을 의미한다. (0은 false, 1은 true를 의미)
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, 주어진 비교 함수로 정렬했을 때, 도치의 개수가 최소가 되는 순열을 출력한다. 그 다음 줄에는 그 순열에서 도치의 개수를 출력한다. 만약, 도치의 개수가 같은 순열이 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다.
예제 입력 1
4 0111 0000 0100 0110 3 011 011 011 6 101010 011010 110110 000000 111010 001010 0
예제 출력 1
0 3 2 1 0 0 1 2 1 0 1 5 2 3 4 5
출처
ICPC > Regionals > North America > Rocky Mountain Regional > 2012 Rocky Mountain Regional Contest E번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호