백준 문제 14398번 피타고라스 수 문제풀이 c++

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

14398번: 피타고라스 수

 

문제해석

 

피타고라수 수는

a=m^2-n^2 , b=2mn ,c=m^2+n^2 를 (m>n, m,n은 정수)를 만족하는 세 쌍이다.

 

b는 무조건 짝수인데 a는 짝수도 가능하고 홀수도 가능하다.

1.하지만 문제의 조건에 최대공약수가 1이 되게끔 만족하려면 a는 무조건 홀수여야한다.

2.그 후 그 둘이 피타고라스의 정의를 만족하는 정수인가를 확인한다.

 

위 조건을 만족한다면 둘이 인접하다(==매칭가능하다)라고 adj배열에 표시를해준다.

이제 이 adj배열을가지고 최대 매칭을 해주어야하는데 그 부분을 몰라서 알고리즘 분류 태그를 열어보았는데 이분 매칭이란것이 있었다.

이분매칭 알고리즘은 몰랐기 때문에 그 부분은 검색을 통해 찾아보았고 그걸 바탕으로 adj배열을 가지고 이분 매칭을 하였다.

 

이분매칭을 이해한 바에 따르면 두개의 집합 그룹으로 나누고(이 문제에선 짝수와 홀수인듯??)

매칭가능한 상대가 아직 짝이 없거나 짝이 있더라도 상대의 짝이 다른 짝을 선택할 수 있으면 걔는 다른 짝이랑 연결해주고 얘는 처음 매칭 가능하다고 한애랑 연결해준다.

말로 설명하려니 좀 이상한거 같은데 그림으로 보면

A랑 C랑 매칭이 가능한가? yes -> C가 아직 짝이없으므로 A랑 C를 짝지어줌

B랑 C랑 매칭이 가능한가? yes -> C가 이미 A랑 짝을 이루고 있음 C의 짝 A가 다른 녀석하고 짝을 맺을수있나 확인해 본 결과 A는 D랑도 짝을 맺을수있음

그래서 A와 C매칭을 끊고 A와 D랑 짝을 이루게해주고 B랑 C를 맺어준다.

만약 C의 짝 A가 다른 녀석하고 짝을 맺을수있나 확인해본결과 불가능하다면 B랑 C는 짝을 맺어 줄 수없다.

이런 느낌이다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string.h>
typedef long long int ll;
using namespace std;
bool check(ll n, ll m);
ll gcd(ll n,ll m);
bool dfs(ll x);
vector <ll> v;
//vector <ll> odd;
//vector <ll> even;
ll matching[201];
bool visited[201];
bool adj[201][201];
ll ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll n;
    cin>>n;
    v.push_back(-1);
    for(ll i=0; i<n; i++)
    {
        ll input;
        cin>>input;
        v.push_back(input);
    }
    for(ll i=1; i<v.size(); i++)
    {
        if(v[i]&1)
        {
            continue;
        }
        for(ll j=1; j<v.size(); j++)
        {
            if(!(v[j]&1))
            {
                continue;
            }
            if(gcd(v[i],v[j])==1&&check(v[i],v[j]))
            {
                adj[i][j]=1;
            }
        }
    }
    for(ll i=1; i<v.size(); i++)
    {
        memset(visited, 0, sizeof(visited));
        if(dfs(i))
        {
            ans++;
        }
    }
    cout<<ans;
}
bool dfs(ll x){
    if(visited[x]==1)
    {
        return 0;
    }
    visited[x]=1;
    for(ll i=1; i<v.size(); i++)
    {
        if(adj[x][i])
        {
            if(!matching[i]||dfs(matching[i]))
            {
                matching[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
ll gcd(ll n,ll m){
    if(n>m)
    {
        ll tmp=m;
        m=n;
        n=tmp;
    }
    if(n==0)
    {
        return m;
    }
    else
    {
        return gcd(m%n,n);
    }
}
bool check(ll n, ll m){
    ll k=(ll)sqrt(n*n+m*m);
    if(n*n+m*m==k*k)
    {
        return true;
    }
    else
    {
        return false;
    }
}