Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 |
Tags
- https
- 그래픽노블
- 먹방
- 게임
- 컴퓨터네트워크
- C#
- 스팀
- Python
- 프로젝트오일러
- 퍼즐게임
- codility
- lambda
- 몽골여행
- Project Euler
- 우분투
- 워킹데드
- 블라디보스토크
- pycon
- github
- 인디게임
- 중국맛집
- 알고리즘
- API
- FPS
- django
- 파이썬
- coursera
- flask
- certbot
- AWS
- Today
- 19
- Total
- 323,616
YUDA't
[Project Euler 39] 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는? 본문
세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.
{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마입니까?
피타고라스 정의를 이용하는 문제.
일단 수도코드
#1차) 101.58초(왓더...)
#2차) 24.49초. a, b for loop를 전부 도는 대신 p/2로 변경
#3차) 23.42초. math.ceil() 대신 round를 씀. 다른 것도 math.sqrt()를 써봤는데 안 쓰는 게 더 빠른 듯하다.
#4차) 12.57초. 여기서부터는 로직이 아니라 수학(이걸 수학이라 부를 수 있다면.)이 들어감. p를 돌릴 때, 1000까지 다 찾지 말고, 짝수만 찾음. 짝수가 당연히 경우의 수가 많을테니.
>>> 같은 로직이라도 수학을 알면 훨씬 빠르게 짤 수 있다.
>>> 가장 큰 값이 되는 p 값을 뽑아내보니 전부 12의 배수였다.
>>> p의 for loop를 12의 배수만 돌리면 2초 정도로 줄지만, 왜 12의 배수인지 완벽히 이해하지 못했으므로 짝수만 돌린다.
'개발 > 알고리즘 문제' 카테고리의 다른 글
[try helloworld level 1] 최대공약수와 최소공배수 (0) | 2016.06.02 |
---|---|
[Project Euler 40] 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기 (0) | 2016.05.06 |
[Project Euler 38] 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자 (0) | 2016.05.04 |
[Project Euler 32] 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합 (0) | 2016.05.02 |
[Project Euler 37] 왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은? (0) | 2016.04.29 |
- Tag
- Project Euler 39, Python, 프로젝트오일러 39, 피타고라스 정리
0 Comments