[백준] 2437번 - 저울 (C++/파이썬)

문제) 백준 - 그리디 알고리즘 (Greedy) - 저울

-> www.acmicpc.net/problem/2437

2437번: 저울

 

문제를 오랜 시간 관찰했지만... 누적합이라는 느낌은 왔지만 알고리즘의 핵심을 찾지 못했다. 결국 3일 고민후, 답을 봤지만... 이건 뭐 풀이가 이해가 가지 않았다. 수학적 귀납법스러웠는데 쉽게 납득이 되지 않았다. 그러던 중 엄청난 풀이를 발견했다.

백준 2437 풀이 및 해설 (aerocode.net)

백준 2437 풀이 및 해설

 

 

1	2	3
1	2	3	X	5	6	7	8

위의 표를 보면 1~3까지 측정 가능하다고 하자. 만약 무게가 5짜리 추가 들어온다면, 우리는 1~3까지 측정 가능했으니 그 범위에 5를 더하면 된다. 이렇게 되면 4에 해당하는 범위에 비어버리므로 답은 4가 된다.

 

 

이 게시물을 보고 묵은 때가 내려간 느낌이였다. 수직선을 이용한 다른 해석인데 보면서 경이로운 수준이었다.(물론 내 실력이 *밥이기도 하고...)

저 핵심을 바탕으로 다시 코드를 짜니 너무 간단한 문제.

 

 

C++ 소스 코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	using namespace std;
	vector <int> chu;
	int main() {
	ios::sync_with_stdio(false);
	cout.tie(0); cin.tie(0);
	int n; cin >> n;
	chu.resize(n);
	for (int i = 0; i < n; ++i) cin >> chu[i];
	sort(chu.begin(), chu.end());
	int target = 1;
	for (int i = 0; i < n; ++i) {
	if (target < chu[i]) break;
	target += chu[i];
	}
	cout << target << endl;
	return 0;
	}

view raw 2437.cpp hosted with ❤ by GitHub

 

 

파이썬 소스 코드)

 

	import sys
	input = sys.stdin.readline
	n = int(input())
	weight = list(map(int, input().split()))
	weight.sort()
	target = 1
	for i in weight:
	if target < i:
	break
	target += i
	print(target)

view raw 2437.py hosted with ❤ by GitHub