[백준] 2437 저울

0

백준

목록 보기
59/271
post-thumbnail

⚡백준 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][0,1]
    (2) 사용하는 추 : 1 1
    -> 측정할 수 있는 무게의 구간: [0,1]+[1,2]=[0,2][0,1] + [1,2] = [0,2]
    (3) 사용하는 추 : 1 1 2
    -> 측정할 수 있는 무게의 구간: [0,2]+[2,4]=[0,4][0,2] + [2,4] = [0,4]
    (4) 사용하는 추 : 1 1 2 3
    -> 측정할 수 있는 무게의 구간: [0,4]+[3,7]=[0,7][0,4] + [3,7] = [0,7]
    (5) 사용하는 추 : 1 1 2 3 6
    -> 측정할 수 있는 무게의 구간: [0,7]+[6,13]=[0,13][0,7] + [6,13] = [0,13]
    (6) 사용하는 추 : 1 1 2 3 6 7
    -> 측정할 수 있는 무게의 구간: [0,13]+[7,20]=[0,20][0,13] + [7,20] = [0,20]
    (7) 사용하는 추 : 1 1 2 3 6 7 30
    -> 측정할 수 있는 무게의 구간: [0,20]+[30,50][0,20] + [30,50]
    -> [21,29][21,29] 구간의 무게는 측정할 수 없다

  • 지금까지 구간이 끊기지 않았다면, 기존 구간: [0,psum[i1]][0, psum[i-1]]
    -> 무게가 weights[i]인 추가 더해진다면, 새롭게 생긴 구간: [weights[i],psum[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;
}

📌참고자료

profile
Be able to be vulnerable, in search of truth

0개의 댓글