32
2015-05-14 03:11:10
0
//내맘의눈
열의어린 풀이 굉장히 감사드립니다.
이 문제는 반으로 나누어 두개의 버블소트로 해석하는 것이 가장 쉽습니다. 또한 결과값에서 정수형의 특성에 기반한 약간의 최적화도 할 수 있습니다.
어떤 n개의 오름차순(또는 내림차순)의 수열을 버블소트로 완전 역순으로 만들기 위해서는 n(n-1)/2의 횟수가 필요합니다.
문제의 답은 원탁을 n이 짝수면 반으로, 홀수면 반에 가깝게 둘로 나누어 역순으로 만드는 횟수를 합하면 됩니다.
정리해보면 n이 짝수인 경우 (n^2 - 2n)/4이고, 홀수인 경우 (n-1)^2/4입니다. 이렇게 짝수와 홀수의 답이 나뉘게 되는데, 짝수의 경우 구한 답에서 1/4를 더해 제곱수로 만들어도 정수형이므로 결과값에는 차이가 없고, 이는 홀수인 경우의 답과 같습니다.
따라서 짝수, 홀수인 경우 모두 --n*n/4만으로 답을 구할 수 있습니다.
늦은 시간에 그림까자 첨부해주신 열정적인 풀이 정말 감사드립니다.