[백준] 2437 저울

⚡백준 2437 저울

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

• 첫 번째 코드 (메모리 초과 & 시간 초과)
  -> 2중 for문의 수행 횟수 최대 1,000(추의 개수) $*$ 1,000,000,000(bool 배열 크기)
  -> 약 10,000초 ㅋㅋㅋ

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

typedef unsigned long long int ull;
const ull MAXW = 1000000000;

//possiblew[무게]: 주어진 추로 무게를 만들 수 있는지 없는지 불린값 저장
bool possiblew[MAXW + 1];

bool compare(int a, int b) {
	return a > b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<int> w;

	//주어진 추로 만들 수 있는 최대 무게
	ull maxw = 0;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		
		w.push_back(input);
		maxw += input;
	}

	//추 내림차순 정렬
	sort(w.begin(), w.end(), compare);
	
	for (auto it = w.begin(); it != w.end(); ++it) {
		for (int j = maxw - *it; j > 0; --j) {
			if (possiblew[j]) 
				possiblew[j + *it] = true;	
		}
		possiblew[*it] = true;
	}

	for (int i = 1; i <= maxw; ++i) {
		if (possiblew[i] == false) {
			cout << i;
			return 0;
		}
	}
	
	cout << maxw + 1;
	return 0;
}

풀이

• 이 문제의 키 포인트는 추로 측정할 수 있는 무게의 기존 구간과 새롭게 생긴 구간이 연속되는가?를 판단하는 것이다

• ex.
  7
  3 1 6 2 7 30 1
  추의 무게 오름차순으로 정렬: 1 1 2 3 6 7 30
  (1) 사용하는 추 : 1
  -> 측정할 수 있는 무게의 구간: $[0,1]$
  (2) 사용하는 추 : 1 1
  -> 측정할 수 있는 무게의 구간: $[0,1] + [1,2] = [0,2]$
  (3) 사용하는 추 : 1 1 2
  -> 측정할 수 있는 무게의 구간: $[0,2] + [2,4] = [0,4]$
  (4) 사용하는 추 : 1 1 2 3
  -> 측정할 수 있는 무게의 구간: $[0,4] + [3,7] = [0,7]$
  (5) 사용하는 추 : 1 1 2 3 6
  -> 측정할 수 있는 무게의 구간: $[0,7] + [6,13] = [0,13]$
  (6) 사용하는 추 : 1 1 2 3 6 7
  -> 측정할 수 있는 무게의 구간: $[0,13] + [7,20] = [0,20]$
  (7) 사용하는 추 : 1 1 2 3 6 7 30
  -> 측정할 수 있는 무게의 구간: $[0,20] + [30,50]$
  -> $[21,29]$ 구간의 무게는 측정할 수 없다

• 지금까지 구간이 끊기지 않았다면, 기존 구간: $[0, psum[i-1]]$
  -> 무게가 weights[i]인 추가 더해진다면, 새롭게 생긴 구간: $[weights[i], psum[i]]$
  -> 위의 두 구간이 끊어지지 않으려면 weights[i] <= psum[i-1] + 1을 만족해야 한다

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

typedef int unsigned long long ull;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ull weight[1001];

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> weight[i];

	sort(weight, weight + n);

	ull psum = 0;
	for (int i = 0; i < n; ++i) {
		if (weight[i] > psum + 1) {
			cout << psum + 1;
			return 0;
		}
		psum += weight[i];
	}
	cout << psum + 1;
	return 0;
}

📌참고자료

• 백준 2437 저울 풀이
  https://aerocode.net/392