취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25312번 문제인 200% Mixed Juice!이다.
문제는 아래 링크를 확인하자.

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

주어지는 병들을 설탕의 농도가 높은 순으로 정렬하고, 농도가 높은 주스부터 greedy하게 선택해 문제를 해결하자.

양의 정수 a,b,c,d에 대하여 a/b와 c/d와 같은 분수의 값의 크기비교는 ad와 bc의 비교를 이용해 실수연산 없이 해낼 수 있다. 이를 이용해 실수오차의 걱정 없이 문제를 해결하자.

기약분수를 구할 때 필요한 최대공약수는 유클리드 알고리즘(Euclidean algorithm)을 이용해 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll N, M;
vector<pair<ll, ll>> vec; // {설탕질량, 부피}
bool comp(pair<ll, ll>& p1, pair<ll, ll>& p2) {
	return p1.first * p2.second < p2.first * p1.second;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (N--) {
		ll w, v; cin >> w >> v;
		vec.emplace_back(make_pair(v, w));
	}

	sort(vec.begin(), vec.end(), comp);

	ll V = 0, sugar = 0;
	while (V + vec.back().second < M) {
		V += vec.back().second, sugar += vec.back().first;
		vec.pop_back();
	}

	ll v = M - V;
	ll x = vec.back().first * v, y = vec.back().second;
	ll gcdxy = gcd(x, y); x /= gcdxy, y /= gcdxy;
	cout << sugar * y + x << '/' << y;
}