[파이썬 코딩 - Chap.17] 실습 조금 생각하는 피타고라스 정의 문제 풀어보기

파이썬 예제 : 피타고라스 정의

피타고라스의 정의를 알고, 문제를 풀어봅시다.

 

피타고라스의 정의

'피타고라스 정리'라고 들어 보셨나요? 직각삼각형에서, 빗변의 제곱이 두 직각변의 제곱의 합과 같다는 정리입니다.

거기서 나온 '피타고라스 삼조'라는 개념이 있는데요.

피타고라스 삼조란, 피타고라스 정리

를 만족하는 세 자연수 쌍 (a, b, c)입니다.

예를 들어,

이기 때문에 (3, 4, 5)는 피타고라스 삼조입니다.

a < b < ca<b<c라고 가정할 때, a + b + c = 1000a+b+c=1000을 만족하는 피타고라스 삼조 (a, b, c)(a,b,c)는 단 하나인데요. 이 경우, a * b * ca∗b∗c는 얼마인가요?

 

출력 예시

31875000

 

힌트

가장 단순하게 코드를 짜면 이렇습니다.

for a in range(1, 1000):
    for b in range(1, 1000):
        for c in range(1, 1000):
            if a * a + b * b == c * c and a < b < c and a + b + c == 1000:
                print(a * b * c)

이 코드를 막상 실행해 보면, 굉장히 오랜 시간이 걸릴 것입니다.

논리적으로 봤을 때는 정답을 찾아 주는 코드입니다.

하지만 너무 오래 걸려서 사실상 사용할 수 없다고 보시면 되는데요.

 

이런 걸 "비효율적인 알고리즘"이라고 합니다.

알고리즘이 비효율적인 이유를 간단히만 설명드리겠습니다.

a가 가능한 경우는 1부터 999까지, b가 가능한 경우는 1부터 999까지,

c가 가능한 경우는 1부터 999까지인데요. 그러면,

if a * a + b * b == c * c and a < b < c and a + b + c == 1000:
    print(a * b * c)

위 코드가 총 997,002,999번 실행됩니다. 약 10억 번 정도 실행되는 거죠.

더 효율적인 코드를 짜기 위해서 for문을 두 개만 쓰세요.

 

우리는 a + b + c = 1000a+b+c=1000이라는 조건을 지켜야 합니다. 그말인즉슨 c = 1000 - a - bc=1000−a−b라는 거죠. 이 점을 잘 활용해 보세요.

 

정답

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

 

Related References

코딩이 처음이라면, 코드잇

PYTHON 프로그래핑

요약 : sparta coding club, 스파르타 코딩, 코드잇, 노마드 코더, 프로그래밍, 직장인 코딩, 내일 배움 카드 코딩, 밀크티 코딩, 초등 코딩, 아이스크림 코딩, 코딩 소프트웨어, 파이썬 국비 지원, 파이썬 교육