이분매칭6 백준 14398 / C++ https://www.acmicpc.net/problem/14398 14398번: 피타고라스 수 피타고라스 수 (a, b, c)는 다음과 같은 조건을 만족하는 세 쌍이다. a, b, c는 정수이다. a^2 + b^2 = c^2 a와 b의 최대 공약수는 1이다. 영선이는 나무 막대 N개를 가지고 있다. 영선이는 직각 삼각형 모 www.acmicpc.net [ 풀이 ] 이분그래프 모델링을 해보자. 수학적 지식이 좀 필요하다. 만약 a^2+b^2=c^2에서 a, b가 짝수라면, gcd에 모순이다. a, b가 모두 홀수라면 홀수의 제곱은 4로 나눈 나머지가 항상 1이다. 따라서 c^2은 4로 나눈 나머지가 2인 짝수가 되어 모순이다. ( 제곱수는 mod4로 0,1만 가능) (원시 피타고라스 세쌍을 알고 있다면 .. 2022. 8. 17. 백준 11670 / C++ https://www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net [ 풀이 ] 연산결과가 모두 다르게 짝지어야 한다. 이분매칭으로 해결해주면 된다. 이분그래프를 모델링할때 인덱스와 3가지 값을 연결시키면 될 것 같다. 근데 문제는 값이 음수도 나오고 큰 값이 나온다. 어차피 값의 개수는 7500개이하이므로 좌표압축으로 값의 인덱스를 연결시켜주면 된다. 이후 과정은 쉽다. [ Code ] #include using namespace std; usin.. 2022. 8. 17. 이전 1 2 다음