2016/01/26 코드그라운드 문제 : 프로그래밍 경진대회

이건 시간초과로 40점밖에 안나온다. sorting에서 시간을 먹는데 학교에서 배운 O(n^2)알고리즘으로는 무리고

라이브러리 사용해야 하는 것 같다. c에서는 stdlib.h에 있는 qsort가 있다.

static int compare(const void * a, const void * b) {
  return (*(int*)a - *(int*)b);
} 이 함수 추가하고










for (i = 0; i < n; i++) {
 scanf("%d", &tmp);
 arr[i] = tmp;
 }

qsort(arr, n, sizeof(int),compare);//sort + input 

로 변경해주면 0.1초만에 해결된다.




이 문제에서 많이 헤맸는데 마지막 전 점수에서 동점자가 있을 경우를 생각해봐야 몇 점 이상이 우승후보가 될 수

있는지 알 수 있다. 5 6 7 7 7 같은 경우, 5 5 5 5 5 5 6 6 7 7 7 같이 동점자가 다수인 경우들을 생각해봐야한다.




정렬 후에 n~1까지 각 원소에 더해줘서 최대값을 구해야한다. 이 때 나오는 최대값에서 n을 뺀게 마지막 전에 우승

후보가 되기 위한 최소 점수이다.







// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.

#include <stdio.h>

int arr[300000];

int main(void) {

/* 아래 freopen 함수는 input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 input.txt 로 부터 읽어오겠다는 의미의 코드입니다.

    만약 본인 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면

       그 아래에서 scanf 함수를 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.

       또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.

    단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */

// freopen("input.txt", "r", stdin);



setbuf(stdout, NULL);



int TC;

int test_case;

int i,n;

int count,tmp,max,pos;

scanf("%d", &TC);

for(test_case = 1; test_case <= TC; test_case++) {

// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.

count=0,max=0;

scanf("%d", &n);

for (i = 0; i < n; i++) {

scanf("%d", &tmp);

if (i == 0) arr[0] = tmp;

else {

pos = 0;

while (arr[pos] < tmp && pos < i) pos++;

for (int j = 1; j<=i-pos; j++) {

arr[i-j+1] = arr[i-j];

}

arr[pos] = tmp;

}

}//sort + input

for (i = 0; i < n; i++) {

if (arr[i] + n - i > max) max = arr[i] + n - i;

}

// 이 부분에서 정답을 출력하십시오.

printf("Case #%d\n", test_case);

for (i = 0; i < n; i++) {

if (max <= (arr[i]+n)) count++;

}

printf("%d\n", count);

}



return 0; // 정상종료 시 반드시 0을 리턴해야 합니다.

}