[맛있는물회] <알고리즘> 11399번 "ATM"

처음엔 순열을 사용하려고 구글링을 하여 재귀함수를 사용하였다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int arr[1000]; int number; int min=9999; void swap(int *a, int *b) {     int temp;     temp = *a;     *a = *b;     *b = temp; } void makeMin() {     int cnt = 0;     int sum=0;     for (int i = 0; i < number; i++) {         cnt = 0;         for (int j = 0; j <= i; j++)             cnt += arr[j];         sum += cnt;     }     if (min > sum)         min = sum; } int permutation(int n, int r) {     if (r == 0) {         makeMin();         return 0;     }     for (int i = n-1; i >=0; i--) {         swap(&arr[i], &arr[n - 1]);         permutation(n - 1, r - 1);         swap(&arr[i], &arr[n - 1]);     } } int main() {     int i;     scanf("%d", &number);     for (i = 0; i < number; i++)         scanf("%d", &arr[i]);     permutation(number, number);     printf("%d", min);     return 0; } Colored by Color Scripter

cs

재귀를 쓰니 시간초과가 떠서 다시 생각해보았다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int arr[1000]; int number; int min=9999; void makeMin() {     int cnt = 0;     int sum=0;     for (int i = 0; i < number; i++) {         cnt = 0;         for (int j = 0; j <= i; j++)             cnt += arr[j];         sum += cnt;     }     if (min > sum)         min = sum; } quick(int left, int right) {     int i, j, temp;     int pivot;     if (left < right) {         pivot = arr[left];         i = left;         j = right + 1;         do {             do i++; while (arr[i] < pivot);             do j--; while (arr[j] > pivot);             if (i < j) {                 temp = arr[i];                 arr[i] = arr[j];                 arr[j] = temp;                 //swap(&arr[i], &arr[j]);             }         } while (i < j);         //swap(&left, &j);         temp = arr[left];         arr[left] = arr[j];         arr[j] = temp;         quick(left, j-1);         quick(j + 1, right);     } }   int main() {     int i;     int cnt = 0; int sum = 0;     scanf("%d", &number);     for (i = 0; i < number; i++)         scanf("%d", &arr[i]);       quick(0, number-1);     for (int i = 0; i < number; i++) {         cnt = 0;         for (int j = 0; j <= i; j++)             cnt += arr[j];         sum += cnt;     }       printf("%d", sum);     return 0; } Colored by Color Scripter

cs

생각보다 시간이 오래걸렸다.

재귀없이 순열을 구현하려고 생각했는데 잘안되더라.

그래서 조금 참고를 하여서 sorting 후 계산을 하니 값이 나왔다.

!!!!!!!!!!!

자구때 배운 퀵소트를 활용하여 소팅하였따.