[BOJ] 11508번: 2+1 세일

https://www.acmicpc.net/problem/11508

어차피 가격 제일 낮은 건 3개 묶은 거에서 공짜이므로 미리 정렬을 시켜놓고 순차적으로 확인하자.

(예전에 짠 코드라 sort를 직접 구현했다..)

#include <stdio.h>
#include <string.h>

int price[100001];

void quickSort(int arr[], int left, int right);

int main(void)
{
    int n, sum = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i)
        scanf("%d", &price[i]);

    quickSort(price, 0, sizeof(price) / sizeof(price[0]) - 1);
    for (int i = 0; i < n; ++i)
    {
        sum += price[i];
        if (i % 3 == 2)
        {
            sum -= price[i];
        }
    }
    printf("%d\n", sum);

    return 0;
}

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2];
    int temp;
    do
    {
        while (arr[i] > pivot)
            i++;
        while (arr[j] < pivot)
            j--;
        if (i <= j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    } while (i <= j);

    /* recursion */
    if (left < j)
        quickSort(arr, left, j);

    if (i < right)
        quickSort(arr, i, right);
}