[C++] 14398번 피타고라스 수

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

---

 

25/12/03

 

 

이분 매칭 문제이다. 그래프 모델링을 잘 해봐야한다.

---

 

문제 접근 방식:

 

 

나무 막대끼리 서로 매칭시키면 그 간선마다 피타고라스 쌍이 하나씩 만들어짐을 알 수 있다.

 

예를 들어, $3$과 $4$ 길이의 나무 막대를 서로 매칭시키면, $5$짜리의 쇠막대를 이용할 수 있다. 쇠막대는 개수가 무한개이므로 결국 나무막대 2개가 한 쌍을 이루게 된다.

 

따라서, 나무 막대들을 어떻게 2개의 그룹으로 분할할지가 가장 큰 고민이었다.

 

첫번째로 든 생각은, 나무막대를 하나 더 복사해서 매칭을 시키자하는 거였지만, 이미 사용한 막대는 다시 사용할 수 없기 때문에 최대 매칭을 잘못 구할 수 있다.

 

이를 막기 위해 간선을 잘 연결하려고 해도 구현이 복잡해진다.

 

수학적으로 따져보면, 나무 막대를 홀/짝으로 분리하고 간선을 이으면 이분매칭이 가능한데, 그 이유는 다음과 같다.

 

1. 둘 다 짝수인 경우 -> 문제 조건에 의하여 최대 공약수가 $1$이 아니기 때문에 불가능

 

2. 둘 다 홀수인 경우 -> $a^2$과 $b^2$ 모두 $4$로 나눈 나머지가 $1$임 -> $c^2$을 $4$로 나눈 나머지는 $2$임. -> $c^2$은 짝수임 -> $c$는 짝수임 -> $c^2$을 $4$로 나눈 나머지가 $0$임.(이는 이전에 말했던 것과 모순되므로 불가능)

 

따라서 둘의 홀짝성은 다를 수 밖에 없다.

 

이에 맞춰서 홀짝을 분리하고 간선을 이어준 후 이분 매칭을 돌리면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 14398번 피타고라스 수
// 이분 매칭
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;

struct Kuhn{
    int L, R;
    vector<vector<int>> adj;
    vector<int> visited, matchedR;
    Kuhn(int L, int R) : L(L), R(R), adj(L), visited(R, 0), matchedR(R, -1) {};
    void addEdge(int u, int v){adj[u].push_back(v);}
    bool dfs(int u){
        for (int v : adj[u]){
            if (!visited[v]){
                visited[v] = 1;
                if (matchedR[v] == -1 || dfs(matchedR[v])){
                    matchedR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int matching(void){
        int match = 0;
        for (int u = 0; u < L; ++u){
            fill(visited.begin(), visited.end(), 0);
            if (dfs(u)) ++match;
        }
        return match;
    }
};

bool isSquare(ll num){
    ll s = 0, e = 1'000'000'000;
    while (s+1 < e){
        ll m = (s+e)>>1;
        if (m*m > num) e = m;
        else s = m;
    }
    return (s*s == num);
}

ll gcd(ll a, ll b){
    return (b == 0) ? a : gcd(b, a % b);
}

int main(void){
    fastio

    int N; cin >> N;
    vector<ll> stickLength(N);
    for (int i = 0; i < N; ++i) cin >> stickLength[i];
    vector<ll> evenLength, oddLength;
    for (int i = 0; i < N; ++i){
        if (stickLength[i] & 1) oddLength.push_back(stickLength[i]);
        else evenLength.push_back(stickLength[i]);
    }
    int L = evenLength.size(), R = oddLength.size();
    Kuhn kuhn(L, R);
    for (int u = 0; u < L; ++u){
        for (int v = 0; v < R; ++v){
            ll sqaureNumber = evenLength[u]*evenLength[u] + oddLength[v]*oddLength[v];
            if (isSquare(sqaureNumber) && (gcd(evenLength[u], oddLength[v]) == 1)){
                kuhn.addEdge(u, v);
            }
        }
    }
    cout << kuhn.matching();
    return 0;
}