Problem_009_Special Pythagorean triplet

[그림 01] Problem 009 문제

문제 이름 : 특별한 피타고라스 정리

문제 내용 : 피타고라스 정리의 삼각형에서 세 개의 자연수에 대한 설정은 a < b < c이며, a^2 + b^2 = c^2입니다. 예를들면 3^2 + 4^2 = 9 + 16 = 25 = 5^2라고 할 수 있습니다. 그렇다면, a + b + c = 1000일 때 위의 정의에 맞는 a, b, c를 구하고 그의 곱인 a*b*c를 구하시오.

우리는 다음과 같은 조건이 있다는 것을 알 수 있습니다.

1. a < b < c가 성립되어야 함

2. a^2 + b^2 = c^2이 되어야 함

3. a + b + c = 1000이 되어야 함

무작정 소스코드를 작성함에 있어서 많은 어려움이 있습니다...

먼저 손으로 구해본 결과 어떻게 해야할지 몰라서... BruteForcing을 해야 하나 하며 고민한 결과 정말로 BruteForcing을 하기로 했습니다. ㅎㅎ

첫번째 버전의 소스는 다음과 같습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	a = 3
	b = 4
	c = 5
	
	for i in range(a, Limit):
		for j in range(b, Limit):
			for k in range(c, Limit):
				if k**2 == (i**2 + j**2):
					print("A : ", i, " B : ", j, " C : ", k, "A+B+C == ", i+j+k)
					if i+j+k == 1000:
						print(i, " ", j, " ", k) 
						break

첫번째 버전의 소스로 하면 겁나 오래걸립니다. 나오기는 합니다만, 중복되는 계산이 많아서 꽤 걸립니다.

두번째 버전의 소스로 넘어가 보면 조건을 하나 더 걸어보았습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	a = 3
	b = 4
	c = 5
	
	for i in range(a, Limit):
		for j in range(b, Limit):
			if j > i:
				for k in range(c, Limit):
					if k > j:
						if k**2 == (i**2 + j**2):
							print("A : ", i, " B : ", j, " C : ", k, "A+B+C == ", i+j+k)
							if i+j+k == 1000:
								print(i, " ", j, " ", k)
								break

두번째 버전의 소스는 a < b < c 의 조건을 성립시켜주었습니다. 사실 첫번째 소스를 작성할 때 이 조건을 깜빡하고 했습니다. ㅎㅎ

그러나 이렇게 해도 시간은 어어어엄청 걸립니다. a + b + c 의 값이 1000이 되지 않으면 무한 반복이지요...(정확히는 a가 1000이 될 때까지 계속 반복됩니다.)

그렇다면 우리는 시간을 대폭 줄일 필요가 있습니다.

세번째 소스로 보겠습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	half = Limit / 2
	a = 0
	b = 0
	c = 0
	
	while(a < half):
		a += 1
		b = half - a
		
		while(b < half):
			c = Limit - (a + b)
			if c < (a+b) and a**2 + b**2 == c**2:
				print("A : ", a, " B : ", b, " C : ", c, " A*B*C : ", a*b*c)
				b = Limit + 1
				a = b
				
			b += 1

if __name__ == "__main__":
	Main_LimitNumber = 1000
	
	findPythagorean(Main_LimitNumber)
		

반복구간을 결정할 필요가 있습니다.

먼저 a, b, c를 선언하고 초기화 해주고 다음으로 넘어갑시다.

a의 검색 구간을 전체의 반으로 줄여서 1부터 500으로 만들어서 그 반복을 설정합니다.

또한 b는 설정구간을 (절반 - a)로 지정해줍니다.

그 다음 while문으로 넘어가 b가 절반보다 작을 때 조건문을 실행합니다.

<조건문>

1. 삼각형의 기본적인 조건인 가장 큰 변이 두 변의 합보다 작아야 함.

2. 주어진 조건인 a^2 + b^2 = c^2

위의 두 조건이 만족할 때 a, b, c를 각각 출력합니다. 그리고 적절하게 빠져나갈 수 있도록 길을 만들어놓습니다.

만약 위의 조건문이 실행되지 않을 시 b += 1을 실행해주고, while문을 반복합니다.

이렇게 되면 a의 범위 b의 범위 c의 범위 1000 * 1000 * 1000이 아닌 (500 * 501) / 2 * 500으로 빠르게 해결할 수 있습니다.

물론 그 사이사이의 조건 계산과 값 계산을 뺀다면 더욱 빠르게 할 수 있다는 것을 의미합니다.

1초에 할 것을 0.062초만에 하는 것입니다.

저보다 겁나 뛰어난 분의 소스를 가져와보도록 합시다.

for a in range(1, 1000):
     for b in range(a, 1000):
         c = 1000 - a - b
         if c > 0:
             if c*c == a*a + b*b:
                 print(a*b*c)
                 break

겁나게 굉장합니다.

범위를 절반이 아닌 전체로한 것 이외에 조건은 똑같습니다.... 우왕...