[백준] 2437번 저울 - C++

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

2437번: 저울

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

---

    정렬된 수들을 가지고 있을 때 배열을 순회하며 i-1 번째 까지 수들의 합으로 구할 수 있는 수의 최댓값을 sum이라 했을 때 다음 수 arr[i]가 sum+1 이 아닌 더 큰 숫자라면 해당 수들로는 sum+1을 만들 수 없게 된다. 만약 sum+1 보다 작거나 같은 수가 온다면 sum + arr[i]까지의 숫자는 모두 만들 수 있으므로 sum += arr[i]를 해준다.

    예를 들어 sum = 5 인 (1 , 1 , 3)인 경우 1(1),2(1+1),3(3),4(1+3),5(1+1+3) 와 같이 5까지의 숫자는 모두 만들 수 있고 다음 숫자로 6이 들어온다면 7(6 + 1), 8(6+2(1+1)) ,9(6 + 3) ,10(6 + 4(1+3) ), 11 (6 + 5(1+1+3)) 과 같이 만들 수 있다. 

#include <iostream>
#include <algorithm>

using namespace std;

int n,sum=0;
int arr[1001];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		if (sum + 2 <= arr[i]) break;
		sum += arr[i];
	}
	cout << sum + 1;
	return 0;
}

---

    처음에 한 생각은 1~ MAX 값의 배열에 주어진 추들의 숫자로 마킹을 해나가며 마지막에 비어있는 것을 답안으로 해보려 하였지만 고민을 해보니 최댓값이 1,000,000 * 1000 이여서 숫자의 배열에 마킹을 해나가는 방식은 아닐 것이라고 생각했다. 그래서 더 생각을 해봤는데 생각이 나질 않아 구글링의 힘을 빌렸다. 답안 코드를 보는데 코드가 엄청나게 짧았다. 포인트는 sum까지 숫자를 만들 수 있고 sum+1보다 작은 숫자가 들어온다면 두 수의 합까지의 숫자는 생성이 가능하단 것이었다. 재미있는 방법이라 다음번에 이러한 문제가 나온다면 풀 수 있을 것 같다!