프로젝트 오일러: 특별한 피타고라스 삼조

피타고라스 삼조는 자연수 세 개가 a < b < c일 때, 다음을 만족하는 것을 말한다.

a^2 + b^2 = c^2

예를 들어 3^2 + 4^2 = 9 + 16 = 25 = 52

a + b + c = 1000을 만족하는 단 하나의 피타고라스 삼조가 존재하는데 abc의 곱을 찾으라.

풀이 #1

여담으로 Pythagorean triplet이 뭔지 몰라서 찾아보았다. 삼조라는 단어도 처음 듣게 되었는데 피타고라스 쌍 정도로 생각하면 될듯.

어쨌든 문제에서 답은 단 하나가 나온다고 했고, a + b + c가 1000이기만 하면 되므로 단순하게 생각하면, 조합 중 1000이 나오는것을 찾기만 하면 되겠다.

아주 심플하게 풀면 다음과 같다.

#!/usr/bin/env python3

from itertools import combinations

comb = combinations(range(2, 998), 3)

for c in comb:
    if sum(c) != 1000: continue
    if c[0]**2 + c[1] ** 2 == c[2] ** 2:
        print(c)
        break

당연히 전수조사를 하는 코드이므로 시간이 꽤 걸린다. 그러면 이걸 이제 효율적으로 바꿔보자.