프로젝트 오일러 #71 순서가 있는 분수

어려움 정도는 10%로 크게 어려움 없이 풀 수 있는 문제입니다.  분수문제가 연속으로 3문제가 나와있는데, 기약분수를 만드는 것만 잘 이해하면 풀 수 있는 문제들입니다.

 

아래는 이 문제의 원문이 있는 곳입니다.

https://projecteuler.net/problem=71

Problem 71 - Project Euler

분수를 표현하는 방법은 여러가지가 있을 수 있습니다.  그 중 유일한 표현법을 얻기 위해서 기약분수를 사용합니다.

기약분수로 표현을 할 때, 우리는 분수의 크기를 비교할 수 있죠.  그런데, 분모의 상한을 주게되면, 자연수를 나열하듯이 크기별로 숫자를 나열할 수 있습니다.

 

기약분수로 숫자를 나열했을 때, 몇번째 수인지 찾는 것을 물었다면 어려울 수는 있습니다.  이 문제에서는 3/7보다 작은 수 중에 가장 큰 수를 찾는 문제입니다.

 

사실 나이스한 풀이법을 찾은 것은 아니고, 막 생각나는대로 프로그램을 짰습니다.  1,000,000 숫자이면, 그렇게 큰 수가 아닌 관계이고, 분자값을 증가시키면서 자연스럽게 분모값도 증가하도록 하였고, 그렇게 함으로써 3/7과의 차이를 줄이는 방법으로 단순무식하게 찾도록 해봤습니다.

 

아래는 제가 만든 소스입니다.  소스는 참고용으로 봐주세요.

 

//-------------------------------------------------------------------
//  Project Euler #71 - Ordered fractions
//  Author:     Aubrey Choi
//  Date:       2015.04.13.
//  Update:
//              
//-------------------------------------------------------------------
#include <stdio.h>

#define  LIMIT  1000000

int main()
{
  int d = 0, n = 0;
  int save[2];
  double r = 1000.0;

  while(n++ < LIMIT)
  {
    while( n*7 >= 3*d && d <= LIMIT ) d++;
    double s = 3.0/7.0 - (double)n/d;
    if( s < 0.0 ) continue;
    if( s < r ) { r = s; save[0] = n; save[1] = d; }
  }
  printf("%d / %d\n", save[0], save[1]);
}