프로젝트 오일러 9번

Special Pythagorean triplet

Problem 9

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

식을 보니 A Pythagorean triplet는 피타고라스의 정리를 이야기하는 것 같다.

해석

피타고라스의 정리는 a² + b² = c²  를 말하고, 이 식을 만족하고  a + b + c = 1000를 만족하는 a, b, c는 하나다.

a*b*c를 구해라.

분석

피타고라스의 정리를 만족하는 자연수 a, b, c에 대해

1.  a² + b² = c²

2.  a + b + c = 1000

두 개의 식을 이용해 문제를 풀어보자. 우선 생각나는 쉬운 방법은 a, b를 반복문을 통해 구하고 c를 2번 식을 이용해 구한 후

피타고라스의 정리에 들어맞는지 확인하는 방법이다.

코드

flag = False
for a in range(1, 1001):
    for b in range(1, 1001):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a, b, c)
            print(a*b*c)
            flag = True
            break
        if flag:
            break

간단하게 풀기는 했지만 낭비가 심한 느낌. 다른사람의 코드는 나와 많이 다를까 싶어 게시판을 살펴봤다.

n = 1000 
m = -1
for a in range(3, (n//3)+1):
    b = (n**2 - 2*a*n)//(2*n - 2*a)
    c = n - b - a
    if a**2 + b **2 == c**2:
        if a*b*c > m:
            m = a*b*c
print(m)

이 사람은 a만 반복문을 통해 구하고 b도 수식을 이용해 구했다. 

생각해보니 당연한게 a를 반복문을 통해 구한다면 두 개의 수식으로 두 개의 미지수를 푼다는 것인데 풀리는게 맞았다.

변명같지만 이 문제풀 때 인내심이 거의 바닥난 상태였던 것을 인정해야겠다. 지금 너무 춥고 쉬고싶다.

공부를 하기위한 마음으로 한거였지만 생각해보면 아무생각없이 짠 코드로 무슨 공부를 할 수 있을까..,

앞으로는 최소한의 집중력을 가질 수 있는 상태로 공부에 임해야겠다. 하고 또 이 작은 문제에서 느끼는 바가 있다면 되었다.

최종 코드

n = 1000

maxim = -1

for a in range(1, 1000):
    b = (n**2 - 2*a*n)//(2*n - 2*a)
    c = n - b - a
    if a**2 + b**2 == c**2:
        print(a*b*c)
        break