Programming Challenges – 여행 (The Trip)

http://countocram.com/2024/03/07/apfhrxgfl American Express Tramadol 문제 <- 클릭

하면 할수록 채점 로봇이 몹시 까다롭다는것을 느낀다.

https://asperformance.com/uncategorized/c9wurzp43 퀵정렬.. 이론상으로는 알고 있지만 직접 구현하니까 역시 효율적으로 하는것이 만만치 않다. 결국 위키 백과에 있는것을 참고 했다. 사실 제공 되는 함수를 쓰면 되지만 그래도 공부니까..

#include #include #define MAX_STUDENT 1000 using namespace std; void qSort(int* arr, int left, int right) { //기본 제공 되지만... 공부를 위해 int pivot = arr[left]; int left_hold, right_hold; left_hold = left; right_hold = right; while (left < right) { while ((arr[right] >= pivot) && (left < right)) right--; if (left != right) { arr[left] = arr[right]; left++; } while ((arr[left] <= pivot) && (left < right)) left++; if (left != right) { arr[right] = arr[left]; right--; } } arr[left] = pivot; pivot = left; left = left_hold; right = right_hold; if (left < pivot) qSort(arr, left, pivot - 1); if (right > pivot) qSort(arr, pivot + 1, right); } void quickSort(int* arr, int arr_size) { qSort(arr, 0, arr_size - 1); } int main() { int students[MAX_STUDENT]; int average, sum = 0, result = 0; int numberOf1CentMore; int numberOfStudent; double temp; while (scanf("%d", &numberOfStudent) == 1) { if (!numberOfStudent) break; for (int i = 0; i < numberOfStudent; ++i) { scanf("%lf", &temp); students[i] = (int) (temp * 100 + 0.5); //integer로 변환 하면서 0.5를 더해 올림!! sum += students[i]; } quickSort(students, numberOfStudent); //지불한 액수 순으로 정렬 average = sum / numberOfStudent; //평균을 구하고 numberOf1CentMore = sum % numberOfStudent; //나머지는 많이 낸사람들에게 분배 for (int i = 0; i < numberOfStudent - numberOf1CentMore; ++i) { result += abs(students[i] - average); //차액의 절대값 누적 } for (int i = numberOfStudent - numberOf1CentMore; i < numberOfStudent; ++i) { result += abs(students[i] - (average + 1)); //나머지를 1씩 더한 차액을 누적 } result /= 2; printf("$%.2fn", result / 100.0); sum = 0; result = 0; } return 0; }