[맛있는물회] <알고리즘> 2217번 "로프"

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

맨첨에 이중포문으로 O(n^2)로 계속 접근하니깐 시간초과가 계속 떴다.

0000000000000000

0000000000000000 이렇게 있으면 그냥 하나하나마다 자기 값보다 큰 값들을 비교하며 count 해서 계산했었는데 시간초과 계속 떴다.

ㅠㅠ 

그래서 sorting 을 사용해서 조금 더 생각하며 풀었다.

어짜피 로프에 들어가는 무게는 동일하므로 k 값을 n-i로 잡아서 하니 바로 풀렸따 ....

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

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h>   int *arr;   void quick(int left, int right) {     int i, j, pivot, temp;     if (left < right) {         i = left;         j = right + 1;         pivot = arr[left];         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;             }         } while (i < j);         temp = arr[left];         arr[left] = arr[j];         arr[j] = temp;           quick(left, j - 1);         quick(j + 1, right);     } }   int main() {     int cnt = 0;     int i,j,temp;     int max = 0;     int num;     scanf("%d", &num);     arr = (int*)malloc(sizeof(int)*(num+1));     for (i = 0; i < num; i++)          scanf("%d", &arr[i]);       quick(0, num);          for (i = 1; i <= num; i++) {         if (max < (num - i+1)* arr[i])             max = (num - i+1)*arr[i];     }       printf("%d", max);            return 0; } Colored by Color Scripter

cs