11670 - 초등 수학

문제 링크

---

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

문제 요약

---

\(N\)개의 줄에 걸쳐 \(A_i\)와 \(B_i\)가 주어진다. 이 때 각각의 \(A_i\)와 \(B_i\)에 대해 \(+,-,*\)중 하나를 선택해서 나온 결과를 모두 다르게 하고 싶다. 이렇게 연산자들을 선택하는게 가능한지, 가능하다면 어떻게 선택해야 하는지 출력하는 문제다.

문제 풀이

---

\(N\)이 최대 \(2,500\)개가 들어오기 때문에 완전탐색으로는 불가능하다. 우리는 모든 계산의 결과가 유니크해야하다는 것에 주목할 필요가 있다. \(A_i\)와 \(B_i\)의 쌍을 하나의 정점으로 생각하고 \(+,-,*\)한 결과들에 간선을 연결해 보자. 예제 입력을 그래프로 모델링하면 아래와 같은 결과가 나온다.

그렇다면 우리는 우리는 왼쪽의 파란 정점들과 오른쪽에 주황색 정점들을 1:1 매칭시켜주는 문제로 변형시켜서 풀 수 있다. 이 그래프는 이분 그래프이므로 최대 유량 알고리즘을 통해 쉽게 해결할 수 있다.

그렇다면 불가능한 경우는 어떤 경우일까? 최대 매칭의 수가 \(N\)보다 작을 때 불가능한 경우가 될 것이다.

소스 코드

---

#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
int n, cnt, V[2510], aMatch[2510], bMatch[7510];
ll A[2510], B[2510];
map<ll, int> Hash;
vector< vector<int> > node;
 
int getHash(ll num) {
  int& ret = Hash[num];
  if (ret) {
    return ret;
  }
  return ret = ++cnt;
}
 
int add(ll a, ll b) {
  return getHash(a + b);
}
 
int sub(ll a, ll b) {
  return getHash(a - b);
}
 
int mul(ll a, ll b) {
  return getHash(a * b);
}
 
int dfs(int here) {
  if (V[here]) {
    return 0;
  }
  V[here] = 1;
  for (int i = 0 ; i < node[here].size() ; ++i) {
    int there = node[here][i];
    if (bMatch[there] == -1 || dfs(bMatch[there])) {
      aMatch[here] = there;
      bMatch[there] = here;
      return 1;
    }
  }
  return 0;
}
 
int main() {
  scanf("%d", &n);
  node.resize(n);
  for (int i = 0 ; i < n ; ++i) {
    scanf("%lld%lld", &A[i], &B[i]);
    node[i].push_back(add(A[i], B[i]));
    node[i].push_back(sub(A[i], B[i]));
    node[i].push_back(mul(A[i], B[i]));
  }
   
  memset(bMatch, -1, sizeof(bMatch));
  int match = 0;
  for (int i = 0 ; i < n ; ++i) {
    memset(V, 0, sizeof(V));
    if (dfs(i)) {
      ++match;
    }
  }
   
  if (match != n) {
    puts("impossible");
    return 0;
  }
   
  for (int i = 0 ; i < n ; ++i) {
    int ret = aMatch[i];
    ll a = A[i], b = B[i];
    if (ret == add(a, b)) {
      printf("%lld + %lld = %lld\n", a, b, a + b);
    } else if (ret == sub(a, b)) {
      printf("%lld - %lld = %lld\n", a, b, a - b);
    } else {
      printf("%lld * %lld = %lld\n", a, b, a * b);
    }
  }
}