백준 2437번: 저울

[문제 링크]

2437번: 저울

---

어찌보면 간단한 그리디 알고리즘 문제였지만, 솔루션을 생각하기가 쉽지 않은 문제였다.

 

입력받은 추의 무게를 오름차순 정렬한 뒤 가장 가벼운 추부터 무게를 누적한다.

만약 (누적한 무게 + 1) 보다 현재 추의 무게가 더 클 경우 (누적한 무게 + 1)이 측정할 수 없는 무게 중 최솟값이 된다.

---

#include <iostream>
using namespace std;

void Quick_sort(int data[], int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] <= data[pivot])
			i++;
		while (j > start && data[j] >= data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}
		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	Quick_sort(data, start, j - 1);
	Quick_sort(data, j + 1, end);
}

int Greedy(int arr[], int N)
{
	Quick_sort(arr, 0, N - 1);

	if (arr[0] != 1) return 1;

	int sum = 1, ret;
	for (int i = 1; i < N; i++)
	{
		if (sum + 1 < arr[i])
			break;

		sum += arr[i];
	}

	return sum + 1;
}

int main(void)
{
	int N;
	cin >> N;

	int arr[1000];
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << Greedy(arr, N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 118 day