#73 범위안의 분수 세기

이 문제는 난이도 15% 정도의 문제입니다.

 

범위안의 분수를 세는 문제인데요.  프로젝트 오일러 #72 문제와 마찬가지로 분모의 범위가 주어지고, 그 안에서 1/3 와 1/2 사이의 분수의 갯수를 구하는 것입니다.  기약분수라는 조건이 달려있습니다.  즉, 1/3 와 1/2 사이에 2/5, 4/10, 6/15, .. 분수들이 있는데, 4/10, 6/15는 모두 2/5와 같은 분수이기 때문에 카운팅을 하면 안 됩니다.

 

Stern-Brocot Tree

 

프로젝트 오일러 #73 문제는 아래의 링크를 참조하세요.

https://projecteuler.net/problem=73

Problem 73 - Project Euler

 

난이도가 높지 않은 문제는 대충대충 프로그램을 짜도 적절한 시간 안에 답을 낼 수 있습니다.  이 문제도 크게 알고리즘에는 신경쓰지 않았습니다.  제가 짠 프로그램은 답을 계산하기 위해서 850ms 정도의 시간이 소요되었습니다.

 

제가 사용한 알고리즘은 단순합니다.

범위안의 모든 분모값에 대하여 1/3보다 큰 분자값부터 1/2보다 작은 분자값까지 순회하면서 기약분수인지만 검사합니다.  기약분수인지 검사하는 것은 gcd(...) 함수를 작성해서 처리했습니다.  지금 생각해보니 단순 무식하게 짰네요.  조금 더 좋은 알고리즘을 생각할 수 있을 것 같은데말이죠.

 

아래는 제가 짠 소스입니다.  소스는 참조용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  Project Euler #73 - Counting fractions in a range
//    - by Aubrey Choi
//    - created at 2015-04-14
//----------------------------------------------------------------------------------------
#include <stdio.h>
#define  LIMIT  12000

int gcd(int a, int b)
{
  while( b ) { int t = b; b = a%b; a = t; }
  return a;
}

int main()
{
  int count = 0;
  for( int d = 1 ; d <= LIMIT ; d++ )
  {
    int n1 = d/3, n2 = d/2;
    if( d%3 ) n1++;
    for( int i = n1; i <= n2 ; i++ )
    {
      if( i == 1 && (d == 2 || d == 3)) continue;
      if( gcd(d, i) == 1 ) count++;
    }
  }
  printf("ans = %d\n", count);
}