백준 Gold 2 저울

저울 (백준 Gold 2)

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

주어지는 N개의 추들을 이용하여
무게를 ‘젤 수 없는’ 가장 작은 양수의 크기를 구하기

첫 제출 코드

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>

using namespace std;

bool recur(const vector<int>& stat, unordered_set<int>& vSet, int target, int count, int now, int nowStart)
{
	int n = stat.size();
	if (count > n || now > target)
	{
		return false;
	}

	vSet.insert(now);

	if (now == target)
	{
		return true;
	}

	for (int i = nowStart + 1; i < n; i++)
	{
		if (recur(stat, vSet, target, count + 1, now + stat[i], i))
			return true;
	}

	return false;
}

int main()
{
	int n;
	cin >> n;
	vector<int> stat(n);
	unordered_set<int> valueSet;
	for (int i = 0; i < n; i++)
	{
		cin >> stat[i];
		valueSet.insert(stat[i]);
	}

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

	int value = 0;

	while (true)
	{
		value++;
		if (valueSet.find(value) != valueSet.end())
			continue;

		// value를 현재 가진 수들로 만들 수 있는가?
		if (recur(stat, valueSet, value, 0, 0, -1))
			continue;

		break;
	}

	cout << value;

	return 0;
}

시간초과 발생

문제 자체에 주어진 시간이 너무 적었기에
이 방식으로 시간초과가 발생하였다

현재 코드처럼 ‘일일이’ 세는 방법은
정답이 아니며, 뭔가 놓치고 있다고 생각하였다

풀이방법

고려할 점을 다시 생각해 보았다

• 추는 결국 ‘더해서’ 무게를 잰다
  
• 결국 구하는 것은 ‘추로 구할 수 없는 무게’지만
  그 중 ‘가장 작은 값’
  

따라서 첫번째 추부터 생각해보자

첫 추 : w1
- 만약 1보다 크다면
  1이 정답
- 아니라면 일단 다음 후보로는 w1 + 1 을 생각

당연히 가장 작은 자연수는 1이므로
첫 추가 1보다 크다면 1이 정답이다

그렇지 않다면 현재 추를 포함한 다음 값을 고려해야 한다

두번째 추 : w2
- 만약 w2가 w1 + 1 보다 크다면
  w1 + 1 이 정답
- 아니라면 다음 후보로 (w1 + w2) + 1 을 생각

따라서 여태까지의 무게 R(현재 w1 + w2)과 다음 추를 비교하는 방식으로
답을 구할 수 있다

고민할 점
사실 제일 헷갈린 부분인데
‘중간 값’은 고려하지 않아도 되는가?

경우의 수를 봐보자

• 만약 다음 무게 추(Wk)가 R+1 보다 ‘크다면’
  R 이 ‘이전 추’까지의 무게를 사용해 표현 가능한 최대 무게
  따라서 R + 1이 ‘표현 불가능’한 가장 작은 값
  

• 만약 다음 무게 추(Wk)가 R+1 보다 ‘작다면’
  R + Wk 까지 ‘표현 가능’한 수가 됨
  

우리는 ‘오름차순’ 정렬을 사전에 해둠
(사실 처음 값이 R : 0 이기에
w1이 1보다 크다면(R+1) R+1이 정답)

1 1 2 3 …
같은 경우는
R이 1 , 2 , 4 , 7 같은 방식으로 늘어나게 됨
(만들 수 있는 수는 {1,2,3,4,5,6,7})

그러나 만약
1 4 10
이런 경우라면 R이 1에서 끝나버림
그러므로 R + 1 인 2가 정답
(해당 방식은 {1,4,5,10,11,14,15}는 만들 수 있음)

수학적 귀납법을 통하여
표현 가능한 수를 점점 넓혀나가는 방식이다

최종 제출 코드

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> stat(n);
	for (int i = 0; i < n; i++)
	{
		cin >> stat[i];
	}

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

	// 가장 작은추가 1이 아니면 그냥 1이 정답이다
	if (stat[0] > 1)
	{
		cout << 1;
		return 0;
	}

	int value = stat[0];

	for (int i = 1; i < n; i++)
	{
		if (stat[i] > value + 1)
		{
			break;
		}

		value += stat[i];
	}

	cout << value + 1;

	return 0;
}

결과

이번 문제를 통해 그리디 문제는 사실
수학과 논리적인 사고가 기반되어야 풀 수 있다는 사실을
다시 깊게 느꼈다