취미로 코딩하기

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

이번에 볼 문제는 백준 12742번 문제인 혼합물 (Small)이다.
문제는 아래 링크를 확인하자.

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

12743번 문제와 같이 답이 유일함을 가정하겠다. 그리고 편의상 \(GA_i\)는 \(A_i\)로, \(GB_i\)는 \(B_i\)로 표기하겠다.

앞으로 만들 A의 양을 \(x\), B의 양을 \(y\)라 하자. 이 때 \(xA_i + yB_i\le W_i\)가 성립하며, 추가적으로 \(x\ge 0\), \(y\ge 0\)이 성립한다. 이때 주어진 문제는 \(xX+yY\)의 최댓값을 구하는 것으로 해결할 수 있다. 이는 LP(Linear Programming; 선형계획법) 문제로 볼 수 있다. 이 LP 문제를 해결해 문제를 풀어내자.

모든 조건을 만족하는 \(x\)와 \(y\)를 좌표평면 위에 나타내면 볼록다각형의 형태를 띄는데, LP의 해는 이 다각형의 경계에서 항상 찾을 수 있음이 잘 알려져있다. 특히 답이 유일한 경우 LP의 해는 이 다각형의 꼭짓점에서 항상 찾을 수 있다. 문제 조건(입력으로 주어지는 모든 수는 양의 정수)에 따라 해당 다각형은 항상 넓이가 양수임을 관찰하자.

이 다각형의 꼭짓점들은 직선들 \(xA_i + yB_i = W_i\) 및 \(x=0\), \(y=0\)의 교점에서 찾을 수 있으므로, 각 교점에 대하여 해당 교점이 다각형의 꼭짓점인지 판정하고 그 중 xX+yY의 최댓값을 구해 문제를 해결하자. 이 과정에서 두 직선이 평행해 교점이 없을 수도 있음에 유의해 구현하자. 또한 \(x\)축과 \(y\)축을 고려해야 함을 놓치지 말자. 아래의 글쓴이의 풀이는 직선의 쌍 \(O(N^2)\)가지에 대하여 두 직선의 교점이 다각형의 꼭짓점인지 각각 \(O(N)\)에 판정해 총 \(O(N^3)\)의 시간복잡도를 가진다. 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

#include <iostream>
using namespace std;
typedef long long ll;
typedef long double ld;

ll N, X, Y;
ll A[200], B[200], W[200];
ld ans1, ans2, ans;

void solve11(int i) {
	ld XX = (ld)W[i] / A[i];
	ld YY = 0;
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}
void solve12(int i) {
	ld XX = 0;
	ld YY = (ld)W[i] / B[i];
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}

void solve2(int i, int j) {
	if (A[i] * B[j] == A[j] * B[i]) return;
	ld XX = (ld)(W[i] * B[j] - W[j] * B[i]) / (A[i] * B[j] - A[j] * B[i]);
	ld YY = (ld)(W[j] * A[i] - W[i] * A[j]) / (A[i] * B[j] - A[j] * B[i]);
	
	if (XX < 0 || YY < 0) return;
	
	for (int k = 0; k < N; k++) {
		if (XX * A[k] + YY * B[k] > W[k]) return;
	}
	
	ld val = XX * X + YY * Y;
	if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}

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

	cin >> N >> X >> Y;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	for (int i = 0; i < N; i++) cin >> W[i];

	for (int i = 0; i < N; i++) {
		solve11(i);
		solve12(i);
		for (int j = i + 1; j < N; j++) {
			solve2(i, j);
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << ans << '\n' << ans1 << ' ' << ans2;
}