[백준/BOJ] 1246. 온라인 판매 [Silver 5]

1246. 온라인 판매

문제출처 : https://www.acmicpc.net/problem/1246

처음에는 N이 M보다 큰경우 작은경우 나눠서 하나씩더하고... 생 노가다를 했는데...
커피한잔 마시고 뇌를 비우고 다시 푸니까 방법이 보였다.

code

#include <stdio.h>
void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] > arr[piv])
			left++;
		while (right > start && arr[right] < arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, M, i;
	int egg[1001] = { 0 }, temp_price = 0, egg_price = 1000000, total = 0;
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; i++)
		scanf("%d", &egg[i]);
	QuickSort(egg, 0, M - 1);
	for (i = 1; i <=N ; i++)
	{
		if (i > M)
			break;
		temp_price = egg[i - 1] * i;
		if (total <= temp_price && egg[i - 1] <= egg_price)
		{
			total = temp_price;
			egg_price = egg[i - 1];
		}
	}
	printf("%d %d", egg_price, total);
	return 0;
}

내림차순으로 정렬을 하고 달걀의 갯수를 기준으로 반복문을 돌아봤다.
왜냐하면 달걀이 4갠데 5개를 팔순없으니까.
그리고 달걀값의 총합은 어차피 내림차순했으니까 egg[i-1]*i를 해주면 된다...!

정말 처음에는 코드만 100줄넘게 나오고 그랬는데 확실히 다른 방식으로 생각하니까 엄청 쉽게 풀렸다.