[백준/BOJ] 2437. 저울 [Gold 3]

2437. 저울

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

문제푸는데 참고한 블로그 (감사합니다.) : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=hongjg3229&logNo=221627349685

처음에 브루트포스식으로 풀어본코드(시간초과)
code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int N, i,index, weight = 1;

	cin >> N;
	vector<int> v(N);

	for (i = 0; i < N; i++)
		cin >> v[i];

	sort(v.begin(), v.end(), greater<>());

	index = 1;
	while (1)
	{
		weight = index;
		for (i = 0; i < N; i++)
		{
			if (v[i] <= weight)
			{
				weight -= v[i];
			}
		}
		if (weight != 0)
			break;
		index++;
	}

	cout << index;

	return 0;
}

code

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int N, i, sum = 0;

	cin >> N;
	vector<int> v(N);

	for (i = 0; i < N; i++)
		cin >> v[i];

	sort(v.begin(), v.end());

	for (i = 0; i < N; i++)
	{
		if (sum + 1 < v[i])
			break;

		sum += v[i];
	}

	cout << sum + 1;

	return 0;
}

그냥 무지성으로 포문 몇번돌려서 해봤는데, 결과는 나오는데 방대한 테스트케이스를 감당하기에는 시간이 모자랐던것 같다.
그래서 어떻게하면 그리디하게 풀 수 있을까 고민해봤는데, 딱히 눈에 보이는 규칙도 없고 해서.... 다른분들은 어떻게 풀었나 검색해봤는데, 네이버 블로그에 한분이 되게 잘설명해놓은게 있어서 그거보고 이해했다.
귀납법으로 증명까지 해놓으셨던데, 코드를 되게 간결하게 잘짜셨더라..

내 스스로 생각해서 문제를 풀 수 있을때까지 노력해야겠다.