피타고라스 정리는 직각삼각형에서 빗변 c 의 제곱이 두 직각변 a, b 의 제곱의 합과 같다는 정리: c^2 = a^2 + b^2. 기원전 6세기 그리스 수학자 피타고라스가 증명. 피타고라스 수 (Pythagorean triple) 는 이 등식을 만족하는 세 자연수 (a, b, c) 쌍으로 (3, 4, 5) 가 가장 잘 알려짐.
문제 상황과 동기
2D 평면에서 두 점 사이의 거리, 직각 판별, 원의 방정식 등 기하의 거의 모든 곳에서 피타고라스 정리가 쓰임.
Naive 접근: 세 변이 주어졌을 때 a^2 + b^2 = c^2 를 확인하려면 세 변을 정렬한 후 O(1).
핵심 통찰: c 가 항상 가장 크므로 정렬 후 한 번의 검사로 직각 판별 가능.
PS 위치: 두 점 거리의 제곱을 그대로 비교해 실수 연산 회피. 좌표 기하 문제의 가장 기초.
시각화
핵심 아이디어
c^2 = a^2 + b^2직각삼각형:- a, b: 직각변 (legs)- c: 빗변 (hypotenuse), 항상 가장 긴 변Euclid 공식 (primitive triple 생성):a = m^2 - n^2b = 2mnc = m^2 + n^2조건: m > n, gcd(m,n)=1, m-n 은 홀수
알고리즘
is_right_triangle(a, b, c): sides = [a, b, c] 정렬 return sides[0]^2 + sides[1]^2 == sides[2]^2generate_triples(limit): for m = 2..sqrt(limit): for n = 1..m-1: if (m-n) is even: continue if gcd(m, n) != 1: continue a = m^2 - n^2, b = 2mn, c = m^2 + n^2 if c > limit: continue for k = 1; k*c <= limit; k++: output (k*a, k*b, k*c)
구현
// 피타고라스 수 생성 + 직각 판별#include <bits/stdc++.h>using namespace std;int main() { int limit; cin >> limit; vector<tuple<int,int,int>> triples; for (int m = 2; m*m <= limit; m++) { for (int n = 1; n < m; n++) { if ((m-n) % 2 == 0) continue; if (gcd(m, n) != 1) continue; int a = m*m - n*n, b = 2*m*n, c = m*m + n*n; if (c > limit) continue; for (int k = 1; k*c <= limit; k++) triples.push_back({k*a, k*b, k*c}); } } cout << "Found " << triples.size() << " triples:\n"; for (auto& [a,b,c] : triples) cout << a << " " << b << " " << c << "\n"; int x, y, z; cin >> x >> y >> z; vector<int> v = {x, y, z}; sort(v.begin(), v.end()); bool right = v[0]*v[0] + v[1]*v[1] == v[2]*v[2]; cout << (right ? "RIGHT" : "NOT RIGHT") << "\n";}
from math import gcddef generate_triples(limit): triples = [] for m in range(2, int(limit**0.5)+1): for n in range(1, m): if (m-n) % 2 == 0: continue if gcd(m, n) != 1: continue a, b, c = m*m - n*n, 2*m*n, m*m + n*n if c > limit: continue k = 1 while k*c <= limit: triples.append((k*a, k*b, k*c)) k += 1 return tripleslimit = int(input())triples = generate_triples(limit)print(f"Found {len(triples)} triples")for t in triples: print(*t)x, y, z = sorted(map(int, input().split()))print("RIGHT" if x*x + y*y == z*z else "NOT RIGHT")
import java.util.*;import java.io.*;public class Main { static int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int limit = Integer.parseInt(br.readLine()); List<String> out = new ArrayList<>(); int cnt = 0; for (int m = 2; m*m <= limit; m++) { for (int n = 1; n < m; n++) { if ((m-n)%2==0) continue; if (gcd(m,n)!=1) continue; int a = m*m-n*n, b = 2*m*n, c = m*m+n*n; if (c > limit) continue; for (int k = 1; k*c <= limit; k++) { out.add((k*a)+" "+(k*b)+" "+(k*c)); cnt++; } } } System.out.println("Found " + cnt + " triples"); out.forEach(System.out::println); StringTokenizer st = new StringTokenizer(br.readLine()); int[] v = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())}; Arrays.sort(v); boolean right = v[0]*v[0]+v[1]*v[1]==v[2]*v[2]; System.out.println(right ? "RIGHT" : "NOT RIGHT"); }}
💬 댓글