[Python 2.7.3] 위에 좋은 알고리즘이 많아 약간 무식(?) 하지만 적절히 loop를 최소화하는 방법을 써보았습니다.
빗변 c는 a,b보다 작지않으며, 닮은꼴 삼각형을 배제시키기위해서 b 가 a보다 클때만 연산을 수행하면
중복 연산을 피할 수 있다고 생각했습니다. a+b+c가 1000 이상이면 c를 더 이상 진행 시킬 필요가 없고, b,c의 loop 시작 index를
아래 코드처럼 정의하면1000^3 보다는 훨씬 적은 횟수로 돌 수 있네요.
```{.python}
pp = [0]*1001
for a in range(1,1000) :
for b in range(a,1000) :
for c in range(b,1000) :
_sum = a+b+c
if _sum <= 1000 :
if (c*c)==(a*a+b*b) :
temp = pp[_sum]
pp[_sum] = temp+1
print "a,b,c = ",a,b,c
print "pp and sum",pp[a+b+c], a+b+c
else :
break
temp = max(pp)
for i in range(1001) :
if temp==pp[i] :
print i,temp
```
제 노트북에서 18초 나오네요..
840 8
18.0680000782
[Python 2.7.3] 위에 좋은 알고리즘이 많아 약간 무식(?) 하지만 적절히 loop를 최소화하는 방법을 써보았습니다.
빗변 c는 a,b보다 작지않으며, 닮은꼴 삼각형을 배제시키기위해서 b 가 a보다 클때만 연산을 수행하면
중복 연산을 피할 수 있다고 생각했습니다. a+b+c가 1000 이상이면 c를 더 이상 진행 시킬 필요가 없고, b,c의 loop 시작 index를
아래 코드처럼 정의하면1000^3 보다는 훨씬 적은 횟수로 돌 수 있네요.
```{.python}
pp = [0]*1001
for a in range(1,1000) :
for b in range(a,1000) :
for c in range(b,1000) :
_sum = a+b+c
if _sum <= 1000 :
if (c*c)==(a*a+b*b) :
temp = pp[_sum]
pp[_sum] = temp+1
print "a,b,c = ",a,b,c
print "pp and sum",pp[a+b+c], a+b+c
else :
break
temp = max(pp)
for i in range(1001) :
if temp==pp[i] :
print i,temp
```
제 노트북에서 18초 나오네요..
840 8
18.0680000782