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 there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?
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
1/3과 1/2 사이에는 분수가 3개 있는 것을 알 수 있다.
d가 12,000이하인 경우 1/3과 1/2 사이에는 정렬된 약분된 진분수가 몇 개 있는가?
--------------------------------------------------------------------------
71번 문제가 72번 문제에 이어 또다른 형태로 변형되어 나왔다. 앞의 3줄은 같고 마지막 문제 부분만 바뀌어 있지만 그 한 줄을 풀기 위해서는 또다른 방식으로 접근해야 한다. 72번에서는 실행 시간을 줄이는 방법이 떠오르지 않는데, 이번 문제는 71번 문제 해결 방법을 조금만 변형하면 해결가능할 것 같아 먼저 해결해 보기로 했다.
분모 기준 1/3 주변의 분자값에서 시작해서 1/2 주변의 분자값까지 비교하는 형태로 해서 비교 범위를 줄인 덕분에 빠른 성능은 아니지만 brute force에 가까운 방식으로도 답을 구할 수 있다.