[BAE/<JOON> 문제풀이] 2437. 저울

핵심::
물건의 무게 순으로 정렬했을 때 sum(arr[0] ~ arr[i - 1]) + 1 >= arr[i] 를 만족한다면 그 사이의 무게 값들은 모두 만들 수 있다.

풀이::
풀이 보고 품

문제 보자마자 숫자판 마술이 생각나긴 했는데 증명을 못하니까 해결이 힘들었다.

 

핵심 과정 증명은 다음과 같다.

 

명제 :  물건 n개가 있으며 무게 순으로 정렬한 모든 물건에 대해 sum(arr[0] ~ arr[i - 1]) + 1 >= arr[i] 가 만족함.

 

현재 사용 가능한 모든 숫자의 합보다 큰 수를 만들기 위해서는 무조건 새로운 수가 필요하다.

 

우리는 모든 양의 정수를 만들어야하므로 합 k까지의 모든 정수를 만들었다면 다음으로 필요한 새로운 수는 반드시 k + 1 이 될 것이다. 그 이상의 수 p 가 주어진 경우 k + 1은 절대 만들 수 없음이 자명하다. ( p 는 k + 1 보다 크므로 k + 1을 만들 수 없고 그 이전의 수들의 합은 k이므로 )

 

반대로 k + 1 보다 작은 수 p 가 주어졌을 경우, 1부터 k 까지의 합은 모두 만들어져 있으므로 

p ( = k + 1 ), p + 1, p + 2 ... , p + k 로 sum(arr[0] ~ arr[n + 1]) 까지의 모든 합을 구할 수 있다.

 

이러한 특성은 재귀적으로 적용되므로 결국 명제
물건의 무게 순으로 정렬했을 때 sum(arr[0] ~ arr[i - 1]) + 1 >= arr[i] 를 만족한다면 그 사이의 무게 값들은 모두 만들 수 있다.

가 참이 된다.

 

반대로 순서대로 정렬한 배열 arr의 구간 합을 구한 psum 배열에 하나라도 psum[i - 1] + 1< arr[i]인 구간이 있다면 그 이상의 수는 절대로 만들 수 없다. 

 

의견::

그리디 극혐

 

코드::

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int main()
{
	int n; cin >> n; vector<int> arr(n + 1), psum(n + 1);
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		tot += arr[i];
	}

	sort(arr.begin(), arr.end());
	
	for (int i = 1; i <= n; i++) {
		psum[i] = psum[i - 1] + arr[i];
	}

	for (int i = 1; i <= n; i++) {
		if (psum[i - 1] + 1 < arr[i]) {
			cout << psum[i - 1] + 1;
			return 0;
		}
	}

	cout << psum[n] + 1;
	
	return 0;
}