본문바로가기
[오일러 프로젝트] 직각삼각형을 가장 많이 만드는 둘레는?
수학동아 2021.01.04 20:38

코.알.못 홍 기자의 코딩 도전기

코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갑니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 파이썬 모두 정복할 수 있지 않을까요?

 

 

에-하! 수학동아 폴리매스 캐릭터 에프매스의 얼굴로 2021년의 해가 떠오릅니다!

잠깐 눈을 감고 올해에 이루고 싶은 것 또는 갖고 싶은 것 등을 빌어볼까요?

저도 소원을 하나 빌었어요. 앞으로 코딩 더 잘하게 해달라고요!

 

 

<오일러 프로젝트 39번>

어떤 직각삼각형의 세 변이 자연수 a, b, c일 때,

직각삼각형의 둘레 a+b+cp라고 합니다.

예를 들어 p가 120일 때 가능한 a, b, c의 순서쌍은

(20, 48, 52), (24, 45, 51), (30, 40, 50)입니다. 

즉, 3개의 직각삼각형이 가능한거죠.

그럼 1000 이하의 p에 대해 직각삼각형을 가장 많이 만드는 p는 얼마일까요?

 

이번 문제는 피타고라스의 정리에 오일러 프로젝트 39번의 a+b+c=p라는 조건을 대입해 해결할 수 있습니다. 그리고 이 식들을 잘 정리하면 자연수 b가 아래의 식을 만족해야 한다는 것을 알 수 있는데요, 이 식을 이용해 문제를 풀어보겠습니다!

 

 

도전! 오일러 프로젝트 39번 문제 뽀개기

문제를 푸는 데 필요한 파이썬 명령어를 자세히 살펴보기 전, 전체 코드를 한번 살펴봅시다.

앞서 설명했던 수학적인 원리가 어떻게 코드로 표현됐는지 유심히 살펴보세요!

* 코딩 언어는 Python으로 두고 실행하세요!

 

 

#1 파이썬 프로그램에 저장돼 있는 수학 명령어를 불러오기 위해 math 모듈을 실행합니다.

#2 직각삼각형의 둘레 p가 1000 이하의 자연수일 때 각각 가능한 직각삼각형의 경우의 수를 찾기 위한 함수 e039(N=1000)를 정의합니다.

#3 p값을 바꿔가며 찾을 직각삼각형을 가장 많이 만드는 경우의 수(max_cnt)와 그때 p(max_p)의 초깃값을 0으로 둡니다.

#4 세 변 중 a의 최댓값을 계산할 때 p를 나눌 값 2+√2(M)를 미리 계산합니다.

#5 a, b, c가 모두 자연수인 직각삼각형 중 p가 가장 작은 경우는 (3, 4, 5)이므로 p를 3+4+5=12부터 증가시킵니다.

#6 각각의 p에서 만들 수 있는 직각삼각형 개수(cnt)의 초깃값을 0으로 둡니다.

#7 a는 1부터 p/M까지 바꿉니다. range 함수는 항상 (시작값, 끝값+1)로 나타낸다는 점에 유의합니다.

#8 b를 나타내는 분수의 분자가 분모로 나눠떨어지는 자연수인지 확인합니다.

#9 #8의 조건을 만족한다면 cnt에 1을 더합니다.

#10, 11 어떤 p에 대해 가능한 직각삼각형의 개수를 셌다면, 현재의 최댓값보다 더 많이 만들어졌는지 확인합니다. 현재의 최댓값보다 큰 결과가 나오면, 최댓값(max_cnt와 max_p)을 바꿔줍니다.

#12 12부터 1000까지 p를 바꾸며 얻은 max_cnt와 max_p를 돌려줍니다.

#13 e039 함수를 실행해 오일러 프로젝트 39번의 답을 출력합니다.

 

 

파이썬 완전정복! ‘수학으로 가능한 경우의 수 찾기’

39번 문제를 해결하는 데 필요한 파이썬 명령어입니다.

꿀팁 중의 꿀팁, 밑줄 쫙! 핵심만 소개하니 꼭 익혀두세요!

 

1. pa를 바꿔가며 가능한 경우의 수 찾기

세 변의 길이를 모두 자연수로 갖는 직각삼각형 중 둘레가 가장 작은 경우는 (3, 4, 5)입니다. 따라서 둘레 p를 12부터 시작해 1000까지 그리고 a를 1부터 1000까지 바꿔가면서 경우의 수를 찾는 코드를 만듭니다.

 

 

2. pa의 검색 범위 줄이기

조금 더 짧은 시간 안에 문제를 풀기 위해 변수 pa를 한번 살펴보겠습니다. 먼저 p=a+b+c입니다. 그리고 동시에 a2+b2=c2이죠. 이때 ab는 홀수이거나 짝수일 텐데, 이때 다음이 성립합니다.

 

 

직각삼각형의 둘레 p는 항상 짝수이므로, 12부터 1000까지의 짝수에 대해 실행하면 됩니다. 또 직각삼각형의 세 변 중 a가 최댓값을 가지는 경우는 a=b인 직각이등변삼각형입니다. 이때 빗변의 길이 ca2+b2=a2+a2=2a2=c2을 만족하는 √2a이므로, p=2a+c=2a+√2a=(2+√2)a입니다. 따라서 a= p/(2+√2)로 최댓값을 정할 수 있죠. 이렇게 pa의 조건을 개선하면 아래와 같습니다.

 

 

 

2021년 새해의 시작에 맞게

수학에 없어서는 안 되는 피타고라스의 정리를 이용한 문제를 풀어봤습니다.

위의 코드를 응용해서 39번 문제를 한번 풀어보고,

이를 이용해 풀 수 있는 문제를 공개 댓글로 달아주세요!

 

첫 댓글의 주인공이 되어 보세요!
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911