취미로 코딩하기

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

이번에 볼 문제는 백준 11670번 문제인 초등 수학이다.
문제는 아래 링크를 확인하자.

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

N(<=2500)개의 숫자쌍이 주어질 때, 이 숫자쌍들 사이에 +, -, *들을 적절히 넣어 각 계산식의 결과들이 다르게 만드는 문제이다.

나올 수 있는 세 가지 결과값들을 map 등을 이용하여 압축한 후 최대 이분매칭을 이용하여 문제를 해결하자.

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

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

vector<int> G[2501];
map<ll, int> mp;
ll queries[2501][2];

int visited[2501];
int matching[7501];
int bipartite(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bipartite(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

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

	int idx = 1;
	int N; cin >> N;
	for (int i = 1;i <= N;i++) {
		ll x, y; cin >> x >> y;
		queries[i][0] = x, queries[i][1] = y;
		if (mp.find(x + y) == mp.end()) {
			mp.insert({ x + y,idx });
			idx++;
		}
		if (mp.find(x - y) == mp.end()) {
			mp.insert({ x - y,idx });
			idx++;
		}
		if (mp.find(x * y) == mp.end()) {
			mp.insert({ x * y,idx });
			idx++;
		}
		G[i].push_back(mp[x + y]);
		G[i].push_back(mp[x - y]);
		G[i].push_back(mp[x * y]);
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ans += bipartite(i);
	}

	if (ans < N) cout << "impossible";
	else {
		for (int i = 1; i <= N; i++) {
			ll x = queries[i][0], y = queries[i][1];
			if (i == matching[mp[x + y]]) {
				cout << x << " + " << y << " = " << x + y << '\n';
			}
			else if (i == matching[mp[x - y]]) {
				cout << x << " - " << y << " = " << x - y << '\n';
			}
			else {
				cout << x << " * " << y << " = " << x * y << '\n';
			}
		}
	}
}