[백준 - 2437] 저울

||문제 이해

주어지는 여러 무게의 추를 조합하여 만들 수 없는 최소 무게를 구해라

---

||해결 계획

Greedy를 사용한다.

 

오름차순으로 정렬 후, [ i번째 까지의 누적합 + 1 < i번째 추의 무게 ] 가 true면

i번째 까지의 누적합 + 1이 정답이다.

---

||계획 검증

만들수 있는 최대 무게를 m이라 가정한다.

그럼 0 ~ m 의 무게를 만들수 있다.

 

여기서 무게 k인 추를 추가할 때 k가 m보다 + 1만큼 무겁다고 가정하자.

그럼 다시 만들수 있는 무게는 0, 1, 2, ..... m, k, k+1, k+2, ...... k + m 이 가능하다.

이런 범위는 k가 k <= m + 1 라면 k + m이하인 무게를 만들수 있는건 변함없다.

 

반면 k가 m보다 + 2만큼 무겁다고 가정한다.

그럼 다시 만들수 있는 무게는 0, 1, 2, ..... m, m + 1, k, k+1, k+2, ...... k + m 이 가능하다.

보다시피 m + 1은 만들수 없는 무게다.

고로 m + 1 < k 면 m + 1이 만들수 없는 최소 무게인것.

 

만들수 있는 무게의 범위는 모든 추의 무게를 합한것과 같다.

예를 들면

추 = { 1, 1, 3, 8 }

i번째까지 추의 누적합 : sum(i)

i번째의 추 : a(i)

 

sum(0) 은 0이다. 여기서 첫번째 무게 1의 추를 추가할 것이다.

sum(0) + 1 < a(1) == false 이므로 만들수 있는 무게는 0 ~ sum(0) + a(1)이다. ( 0 ~ 1)

 

sum(1) 은 1이다. 여기서 두번째 무게 1의 추를 추가할 것이다.

sum(1) + 1 < a(2) == false 이므로 만들수 있는 무게는 0 ~ sum(1) + a(2)이다. ( 0 ~ 2)

 

sum(2) 은 3이다. 여기서 세번째 무게 3의 추를 추가할 것이다.

sum(2) + 1 < a(3) == false 이므로 만들수 있는 무게는 0 ~ sum(2) + a(3)이다. ( 0 ~ 5)

 

sum(3) 은 5이다. 여기서 네번째 무게 8의 추를 추가할 것이다.

sum(3) + 1 < a(4) == true이므로 만들수 없는 최소 무게는 sum(3) + 1 이다. ( 6 )

---

||구현

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int arr[1001];
	int n; cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);

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

---

||되돌아보기

일단 자력으로 풀지 못했고

혼자 생각 못한 이유라면, 이 문제는 가정과 식을 통해 쉽게 추론할 수 있는 문제였는데

내가 아직 식으로 가정 해보는게 서툴러서 도달하지 못했던것 같다.

 

항상 식으로 논리있는 문제풀이를 하려고 계속 노력하고 있지만

이렇게 가정을 아직 많이 해본적은 없어서 좀 더 식으로 서술 하는 법을 배웠다.