백준 11670 / C++

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

11670번: 초등 수학

 

[ 풀이 ] 

연산결과가 모두 다르게 짝지어야 한다. 이분매칭으로 해결해주면 된다. 

이분그래프를 모델링할때 인덱스와 3가지 값을 연결시키면 될 것 같다. 근데 문제는

값이 음수도 나오고 큰 값이 나온다. 어차피 값의 개수는 7500개이하이므로 좌표압축으로 

값의 인덱스를 연결시켜주면 된다. 이후 과정은 쉽다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, a[2555], b[2555];
vector<ll>g[8000], v;
int par[8000], vis[8000];

// 값 k의 idx
int idx(ll k) {
	return lower_bound(v.begin(), v.end(), k) - v.begin() + 1;
}

int match(int x) {
	for (int nx : g[x]) {
		if (vis[nx])continue;
		vis[nx] = 1;
		if (!~par[nx] || match(par[nx])) {
			par[nx] = x;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		v.push_back(a[i] * b[i]);
		v.push_back(a[i] + b[i]);
		v.push_back(a[i] - b[i]);
	}
	// 좌표압축 
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	// i -> 값 3개의 idx
	for (int i = 1; i <= n; i++) {
		g[i].push_back(idx(a[i] * b[i]));
		g[i].push_back(idx(a[i] + b[i]));
		g[i].push_back(idx(a[i] - b[i]));
	}
	int ans = 0;
	memset(par, -1, sizeof(par));
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		ans += match(i);
	}
	// impossible
	if (ans != n) {
		cout << "impossible";
		return 0;
	}
	// possible
	// 최종적으로 par[nx]=x 인 (x,nx)가 인덱스와 결과값 인덱스가 된다.  
	for (int i = 1; i <= n; i++) {
		if (par[idx(a[i] * b[i])] == i) {
			cout << a[i] << " * " << b[i] << " = " << a[i] * b[i] << '\n';
		}
		else if (par[idx(a[i] + b[i])] == i) {
			cout << a[i] << " + " << b[i] << " = " << a[i] + b[i] << '\n';
		}
		else if (par[idx(a[i] - b[i])] == i) {
			cout << a[i] << " - " << b[i] << " = " << a[i] - b[i] << '\n';
		}
	}
}