[BOJ][C++] 2437번 저울

안녕하세요.

오늘은 백준 2437번: 저울(링크)  문제를 풀어보려고 합니다.

 

문제

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

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

 

입력

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

 

출력

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

 

예제 입력

7
3 1 6 2 7 30 1

 

예제 출력

21

 

제한

시간 제한: 1초

메모리 제한: 128MB

 

---

풀이

1. 완전탐색

처음에 완전탐색으로 찾는 방법을 생각해봤습니다.

그러나 추의 개수가 N≤1000, 어떤 무게가 측정 가능한 지는 최대 2^1000 - 1의 경우가 나오므로 당연히 안 풀립니다.

 

2. DP

따라서 조금 더 효율적으로 경우를 구하고자 했습니다.

 

먼저 저울추의 무게를 오름차순으로 정렬합니다.

정렬하는 이유는 측정할 수 없는 양의 최소 무게를 구하는 것이기 때문입니다.

 

정렬한 후에는 먼저 가장 처음 무게추를 골라 측정 가능한 무게에 저장합니다.

이후, 이전의 구했던 측정 가능한 무게들에 현재 무게를 각각 더해주면 새로운 측정 가능한 무게가 구해집니다.

이때 중복되는 값은 넣지 않고 넘어갑니다.

또한 측정 가능한 무게를 구하는 도중, +1씩 증가하는 수열이 되지 않는다면 측정 불가능한 무게가 있다는 뜻이므로 중단하여 결과를 출력하도록 합니다.

 

ex)

7

3 1 6 2 7 30 1

정렬 후 → 1 1 2 3 6 7 3

 

weights에 들어가는 값들:

1. 1
2. 1 1+1 ⇒ 1 2
3. 1 2 1+2 2+2 ⇒ 1 2 3 4
4. 1 2 3 4 2+3 3+3 4+3 ⇒ 1 2 3 4 5 6 7
5. 1 2 3 4 5 6 7 2+6 3+6 … 7+6 ⇒ 1 2 3 … 11 12 13
6. 1 2 3 … 13 7+7 8+7 … 13+7 ⇒ 1 2 3 … 19 20
7. 1 2 3 … 20 1+30 2+30 … 20+30 =? 1 2 3 … 49 50

이때 7)에서 20 다음에 31이 왔으므로 측정 불가능한 무게는 21이 됩니다.

 

그러나 이 방식도 문제가 있는데, 결국에는 모든 경우의 수를 다 저장해야 하므로 메모리 초과가 날 수 밖에 없었습니다.

따라서 더 효율적인 방법이 필요합니다.

 

3. 그리디

위 DP를 통해서 알게된 중요한 사실은, 측정 가능한 무게들이 +1씩 증가하는 수열이 되야한다는 겁니다.

 

즉, 우리가 이전에 올바르게 수열을 구했다면은 그 수열은 +1씩 증가하는 수열입니다.

이때, 우리가 알고 있는 값은 2가지 입니다.

1. 이전 수열의 범위(1~마지막으로 계산한 측정 가능한 무게)
2. 현재 무게추 무게

우리는 이 무게들로 새로운 수열을 만들었을 때, 그 수열 또한 +1씩 증가하는 수열이 되어야합니다.

 

예를 들어 마지막으로 계산한 측정 가능한 무게가 n, 현재 무게추 무게가 m라고 합시다.

1 2 … n , m

이 값들로 새로운 측정 가능한 무게를 계산했을 때, 그 수열은

(1~n) U (m+1 ~ m+n) 이 됩니다.

 

또한 이 수열이 +1씩 증가하는 수열이 되는 지는

1. m+1값이 n+1보다 작거나 같아야함. 즉, m+1 ≤ n+1
2. n+m값이 n+1보다 크거나 같아야함. 즉, n+1 ≤ n+m
3. 혹은, m값이 n+1이 되어야함.

정리하면, 1~n까지의 값과 m을 더해서 n+1이 나오거나, m이 n+1이라면 +1씩 증가하는 수열이 만들어진다는 뜻입니다.

 

만약 그렇지 않다면, 측정 불가능한 최소 무게가 발견되었고 그 값은

(마지막으로 계산한 측정 가능한 무게) + 1

이 됩니다.

 

예외상황

위의 내용은 무게가 1인 추가 있다는 가정하에 진행되는 과정입니다.

만약 1인 무게 추가 없으면, 애초에 1인 무게조차 측정할 수 없으므로 위 과정을 무시하고 바로 1을 출력하면 됩니다.

정답

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	int last = arr[0];
	bool found = last == 1 ? false : true;
	int ans = 1;
	for (int i = 1; i < n; i++) {
		if(found) break;
		if(!(arr[i]+1 <= last+1 && last+1 <= arr[i]+last) && last+1!=arr[i]){
			break;
		}
		last = arr[i]+last;
		ans = last+1;
	}
	cout << ans;
	return 0;
}

---

이렇게 해서 백준  2437번 저울 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!