시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 210 | 84 | 72 | 47.682% |
선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.
선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.
입력의 첫 번째 줄에는 테스트케이스를 나타내는 P(1 ≤ P ≤ 100)가 주어집니다. 이후 이어지는 행에서 각각 테스트케이스에 해당하는 데이터 세트가 주어집니다.
각각 데이터 세트는 조건에서 주어진 대로 삭삽 정렬을 수행해야하며, 독립적으로 처리되어야 합니다. 각 데이터 세트는 최소 두 행 이상이 주어집니다.
첫 번째 행에서 데이터 세트의 번호인 K와 공백 이후 정렬 할 배열의 길이인 N(1 ≤ N ≤ 1000)이 주어집니다.
그 이후 행에서 정렬 할 배열을 구성하는 N개의 양의 정수가 주어지는데, 마지막 행을 제외한 모든 행에서 10개로 이루어진 109 보다 작은 숫자들이 주어집니다. (마지막 행은 10개 보다 적은 숫자들이 주어집니다.)
주어지는 숫자들은 동일한 숫자가 여러 번 주어질 수 있습니다.
각각의 데이터 세트의 번호를 나타내는 K와 공백 이후 최소 삭삽 정렬 과정 수행 횟수를 한 행으로 출력합니다.
3 1 3 1 3 2 2 6 1 5 2 4 3 6 3 23 67890 56312 999999999 12345 23456 38927 45632 100345 98765 23456 87654 43278 23456 117654 321899 25432 54326 217435 26845 31782 33456 41234 56213
1 1 2 3 3 15
예제 입력의 첫 번째 데이터 세트인,
1 3
1 3 2
는 다음과 같은 삭삽 정렬 과정을 거칩니다.
3을 선택하여 삭제하고, 배열의 맨 뒤에 삽입하여
1 2 3
으로 1번의 삭삽 정렬 과정을 수행하여 정렬을 종료하여
1 1
을 출력합니다.
ICPC > Regionals > North America > Greater New York Region > 2016 Greater New York Programming Contest H번