[C++][BOJ] 2437번 저울

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

공부 날짜 : 2025.01.05
정답 참조 여부 : X

n개의 수 중 일부를 합쳐서 수를 만들 때 만들 지 못하는 수 중 최소 값을 찾는 문제

---

만들지 못하는 수 중 최소값을 찾으므로 1이 없다면 답은 반드시 1이다.
여기서 착안해서 정렬을 먼저 시도해 줬는데,

정렬이 되어있다면 i번째 수에서 n까지 만들 수 있다면. 그 다음 수인 i+1은 n+1보다 작은 값이여야 한다.

예를 들어 10까지 모든 수를 만들 수 있다고 가정 했을때 다음 수 가 5라면
15까지는 반드시 만들 수 있다.
하지만, 다음 수가 12라면 11은 만들 수 없게 되므로 정렬하여
i번째 까지 더한 합 보다 i+1의 값이 더 커진다면 그 값이 정답이 되는것이다.

이 아이디어를 그대로 구현하여 제출 하니 정답이 나왔다.

#if 1
#include <iostream>

void merge_sort(int left, int right, int* arr) {
	if (left == right) return;

	int mid = (left + right) >> 1;
	merge_sort(left, mid, arr);
	merge_sort(mid + 1, right, arr);

	int i = left, j = mid + 1, k = 0;
	int* temp = new int[right - left + 1];

	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) temp[k++] = arr[i++];
		else temp[k++] = arr[j++];
	}

	while (i <= mid) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];

	for (int t = 0; t < right - left + 1; ++t)
		arr[left + t] = temp[t];

	delete[] temp;
	return;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);

	int n, arr[1000];
	std::cin >> n;

	for (int i = 0; i < n; ++i) std::cin >> arr[i];

	merge_sort(0, n - 1, arr);

	int sum = 1;
	for (int i = 0; i < n; ++i) {
		if (arr[i] <= sum) {
			sum += arr[i];
			continue;
		}

		break;
	}
	std::cout << sum << '\n';


}

#endif