6719

static int N, K;
static int course[200];
 
static int cmp(const void * p1, const void * p2)
{
    int n1 = *(int *)p1;
    int n2 = *(int *)p2;
 
    return n2 - n1;
}
 
static double solution(void)
{
    double ret = 0;
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++)
        scanf("%d", &course[i]);
 
    qsort(course, N, sizeof(int), cmp);
    for (int i = K - 1; i >= 0; i--)
    {
        ret += course[i];
        ret /= 2;
    }
 
    return ret;
}

문제의 해결책에 대한 힌트는 이미 문제 설명에 있었다.

이를 토대로 강의력이 낮은 것 부터 높은 순으로 듣게 되면 그 능력이 향상되는 것을 알 수 있다.

즉, K개의 강의를 최대한 높을 것들만 오름차순으로 들으면 된다.

예를 들어,

1 2 3 4 5 

가 있고, 3개만 수강 할 수 있을 때,

1 2 3 을 듣는 것과, 3 4 5를 듣는 것에는 얻게되는 실력에 대해 분명한 차이가 있음을 알 수 있다.

 

무작위 적으로 들어오는 이 리스트들을 오름차순으로 정렬해야 하는데,

정렬 알고리즘을 직접 구현하는 것도 좋지만, 제일 빠르다고 알려진 퀵 정렬이 이미 c라이브러리에 있기 때문에 이를 사용하면 된다.

 

그래서 여기서는 qsort 사용에 대해서 한 차례 정리하는 게 좋을 거 같다.

다음은 c라이브러리가 제공하는 qsort의 선언이다.

_ACRTIMP void __cdecl qsort(
    _Inout_updates_bytes_(_NumOfElements * _SizeOfElements) void*  _Base,
    _In_                                                    size_t _NumOfElements,
    _In_                                                    size_t _SizeOfElements,
    _In_ int (__cdecl* _PtFuncCompare)(void const*, void const*)
    );

첫번째 인자는 정렬해야 할 배열의 시작주소

두번째 인자는 해당 배열의 길이,

세번째 인자는 각 원소들의 크기

마지막 인자는 배열 내 원소들을 비교하는 함수이다.

 

그래서 이 함수를 정의하는 것이 제일 중요하다 볼 수 있고, 이 함수는 다음과 같은 규칙을 따라야 한다.

오름차순으로 정렬하고 싶으면 첫번째 매개변수가 두번째 매개변수보다 작은 경우 음수,

큰 경우는 양수,

같으면 0을 반환하면 되는데,

이를 외우기 보다는 다음과 같이 이해하면 훨씬 편한거 같다.

 

1 은 2보다 앞선다. 그래서 1 - 2를 빼면 음수이다.

2 는 1보다 뒤선다. 그래서 2 - 1을 빼면 양수이다.

이를 위해서 작성한 cmp()와 비교해보면 된다.

 

n1=1, n2=2 이면, 음수를 반환하여 오름차순 형식으로 정렬 할 수 있다.

n1=2, n2=1 이면 이번엔 양수를 반환하여 역시 오름차순 형식을 정렬 할 수 있게 된다. 

 

즉, 앞에 원소를 기준으로 해야 한다.