[Project Euler #9][C++] a + b + c = 1000 이 되는 피타고라스 수

문제9: a + b + c = 1000 이 되는 피타고라스 수

문제

세 자연수 a, b, c 가 피타고라스 정리 a² + b² = c² 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a < b < c).

예를 들면 3² + 4² = 9 + 16 = 25 = 5²이므로 3, 4, 5는 피타고라스 수입니다.

a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까?

문제 해결 방법

• 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.
  • 3중 for문을 사용하여
    • 1부터 N(1000)까지 순회를 하며 다음의 조건을 만족시켰을 때의 a, b, c 값의 곱을 ans 변수에 할당하였다.
      • a < b < c
      • (a * a) + (b * b) == (c * c)
      • (a + b + c) == NUM(1000)
• 연산을 빠르게 하도록 하기 위해 register 변수를 사용하여 for문을 순회하도록 하였다.

소스 코드

#include <iostream>
using namespace std;
 
#define N 1000
#define NUM 1000
 
int main() {
    int x, y, z, ans;
 
    for (register int a = 1; a <= N; a++) {
        for (register int b = a + 1; b <= N; b++) {
            for (register int c =  b + 1; c <= N; c++) {
                if ((a * a) + (b * b) == (c * c)) {
                    if ((a + b + c) == NUM) {
                        // cout << a << " " << b << " " << c << endl;                                                         
                        ans = a * b * c;
                    }
                }
            }
        }
    }
    cout << ans << endl;
 
    return 0;
}

정답

31875000

심화 공부

피타고라스 트리플(Pythagorean Triple)

피타고라스 정리 $a^{2}+b^{2}=c^{2}$을 만족시키는 세 양의 정수의 튜플 $(a,b,c)$이다. 즉, 유클리드 기하학의 직각 삼각형의 세 변을 이루는 세 양의 정수의 튜플이다. 예를 들어, $(3,4,5)$는 피타고라스 트리플이다. 원시 피타고라스 트리플(Primitive Pythagorean Triple) 은 피타고라스 트리플을 이루는 세 수가 서로소인 경우 이다.

피타고라스 트리플은 항상 $(m^{2}-n^{2},2mn,m^{2}+n^{2})$ ($m>n>0$) 꼴이다. 이러한 꼴이 원시 피타고라스 트리플일 필요 충분 조건은 $m,n$이 짝수를 포함하는 서로소 정수인 것이다. 특히, $(m^{2}-1,2m,m^{2}+1)$ 은 항상 피타고라스 트리플이다. 여기서 $a=m^{2}-n^{2},b=2mn,c=m^{2}+n^{2}$ 관계는 피타고라스 트리플을 구하는 프로그래밍에서 매우 유용하게 사용된다.

원시 피타고라스 트리플은 $(3,4,5)$로부터 시작하여 아래 세 행렬을 곱하여 얻어낼 수도 있다.

$\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix}, \begin{pmatrix}-1&-2&-2\\2&1&2\\2&2&3\end{pmatrix}, \begin{pmatrix}1&2&2\\-2&-1&-2\\2&2&3\end{pmatrix} $

---

문제 출처 : https://euler.synap.co.kr/problem=9