프로젝트 오일러: 특별한 피타고라스 삼조
프로젝트 오일러: 특별한 피타고라스 삼조
피타고라스 삼조는 자연수 세 개가 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
당연히 전수조사를 하는 코드이므로 시간이 꽤 걸린다. 그러면 이걸 이제 효율적으로 바꿔보자.