피타고라스 수( BOJ 14398 )

문제

14398. 피타고라스 수 : https://www.acmicpc.net/problem/14398

14398번: 피타고라스 수

 

문제 파악하기

• 피타고라스 수란 a² + b² = c²을 만족하는 (a, b, c) 숫자쌍을 의미합니다.
• 이 문제에서는 서로 서로소인 a와 b를 찾는 문제입니다.
• (a, b) 순서쌍의 최대 개수를 묻고 있기 때문에 이분 매칭을 이용해야 한다는 점을 유추할 수 있습니다.
• 이분 탐색을 위해서는 2개의 범주로 나눠야 합니다. 그럼 입력된 숫자들을 어떻게 나눌 수 있을까요?
• 질문에 대한 답을 하기 위해 1 ~ 100까지 피타고라스 수를 쭉 출력해보니 공통점을 찾을 수 있었습니다.

 

문제 해결하기

• 여기서부터는 위키백과(피타고라스 삼조)를 참고했습니다.
• 피타고라스 삼조 (x, y, z)는 자연수 2개(u, v / u>v)로 표현할 수 있습니다.
  x = u² + v²  /  y = 2uv  /  z = u² - v² (단, u와 v는 서로 다른 홀수와 짝수)
• 피타고라스 삼조(x, y, z) 중 가장 큰 수는 x입니다.
  (1) u와 v는 정수이기 때문에 x > z 입니다.
  (2) x와 y는 산술-기하 평균 부등식에 의해 x > y 입니다.
  (3) 따라서 x는 가장 큰 정수입니다.
• 그럼 우리는 y와 z만 구하면 되는데 y는 항상 짝수, z는 항상 홀수입니다.
  (1) y는 2*u*v이기 때문에 항상 짝수입니다.
  (2) z는 (짝수-홀수) 혹은 (홀수-짝수)가 되기에 항상 홀수입니다.
• 따라서 우리는 입력받은 숫자를 짝수와 홀수로 나눈 후 그래프를 만들고 이분 매칭을 하면 됩니다.

 

후기

피타고라스 수라는 어찌보면 친숙한 숫자를 문제로 풀어내서 흥미로웠습니다. 특히 문제 해결에는 사용되지 않았지만 피타고라스 삼조에는 항상 3의 배수를 가지고 있다는 점이 재미있었네요. 이분 매칭을 연습할 수 있는 좋은 문제라고 생각합니다.