Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
n과 d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고 HCF(n,d)=1인 경우, 약분된 진분수라 부른다.
d가 8보다 작거나 같은 경우 크기가 커지는 순서로 약분된 진분수 목록을 구하면 다음과 같다.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
여기에서 2/5는 3/7의 바로 왼쪽에 있는 것을 알 수 있다.
1,000,000 이하의 약분된 진분수를 크기가 커지는 순서로 나열할 때 3/7의 바로 왼쪽에 있는 분수의 분자는 무엇인가?
--------------------------------------------------------------------------
문제에서 요구하는 것을 다시 풀어보면, 분자가 분모보다 작고, 분자, 분모의 최대공약수가 1인 경우 약분된 진분수라 부른다고 정의하고 있으며, 진분수를 크기대로 나열했을 때, 3/7보다 작은 수가 무엇인지 물어보고 있다.
오래간만에 구현하기 간단한 문제가 나와 처음에는 분모가 2~1,000,000일때 까지의 약분된 진분수의 목록을 (분자, 분모, 나눈값)으로 구해서, 그것을 정렬하고, 3/7 바로 앞의 값을 찾는 형태로 구현했는데, 문제에서 제시한 예시를 구현했을 때에는 금방 동작했지만, 분모가 1,000,000일 때 까지 구하도록 하니 파이썬에서 처음 보는 '메모리 에러' 메시지와 함께 중단되었다. 진분수의 목록을 구하는 라인에서 에러가 발생한 것을 보니 수백만 개의 값이 있는 목록을 만드는 것에서 문제가 생긴 것 같다.
그래서, 각 분모값에 대해 분자를 1부터 키워나가면서 3/7에 근접하게 되는 값을 구하도록 접근 방법을 바꿨다. 리스트를 쓰지 않고 단순 계산만 하도록 몇 줄의 코드로 구현되어서 금방 값을 구할 것으로 예상했는데 실행 시간은 생각보다 너무 오래 걸려서 알고리즘 개선이 필요했다.
고민을 해 보니 분모가 커질수록 분자를 1부터 키워나가면서 3/7에 근접하는 값을 구하는 것에서 시간이 많이 소요되는 것을 찾아냈다. 분자가 시작하는 위치를 1에서 답에 가까운 것으로 바꾸었더니 1일 이상 필요할 것으로 예상되었던 시간이 줄어들어 4초 이내에 답을 구할 수 있었다. 더 빠르게 결과를 구하도록 개선 가능하겠지만 일단 이정도에서 만족하기로 했다.
정답 판정 화면에서 해결 과정을 구체적으로 쓰지 말기를 당부하면서 100번 이후 문제를 스포일하면 계정을 잠그겠다고 되어 있다. 해결과정을 조금 더 간결하게 써야겠다.
We hope that you enjoyed solving this problem. Please do not deprive others of going through the same process by publishing your solution outside of Project Euler. Members found to be spoiling problems beyond the first one-hundred problems will have their accounts locked.
If you are keen to share your insights and/or wish to see how other members have solved the problem, then please visit thread 71 in our private discussion forum.