Daily Algorithm - Day 8

Special Pythagorean Triplet

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,

$a^2 + b^2 = c^2.$

For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

There exists exactly one Pythagorean triplet for which $a + b + c = 1000$.
Find the product $abc$.

$a + b + c = 1000$ ($a < b < c$ ) 인 피타고라스 수 $a, b, c$는 한 가지 뿐이고, 이 때의 $abc$를 구하는 문제이다.

바로 생각난 구현 방식은 다음과 같다.

• for 반복문을 3번 중첩해서 모든 조합을 대입해본다.

그러나 생각한 후에 바로 심상치 않음을 느꼈다. 시간복잡도가 $O(n^3)$ ?
우선 해당 코드를 대강 구현한 후에 탐색범위를 줄일 수 있는 요소를 고민해보자.

//Python

for a in range(1,1001):
    for b in range(1, 1001):
        for c in range(1, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:  
                print(a*b*c)

$a+b+c=1000$ 일 떄 $a < b < c$ 라면 $a,b,c$의 범위를 다음과 같이 한정할 수 있다.

1. $a<333$ ($a\geq333$ 일 경우 $a+b+c>1000$)
2. $b<500$ ($b\geq500$ 일 경우 $a+b+c>1000$)
3. $a$와 $b$만 지정된다면 $c = 1000-(a+b)$

이를 코드에 반영한 결과는 다음과 같다.

for a in range(1,333):
    for b in range(a+1, 500): #  a < b
        c = 1000 - a - b
        if a**2 + b**2 == c**2:  # b < c 또한 내포하고 있다.
            print(a*b*c)
         
>>> 31875000

오늘은 여기까지.

-2024.12.28-