[Algorithm] 백준 10253 - 헨리 풀이

풀이

먼저 문제에서 이해한것을 바탕으로 구현하였더니 시간초과가 났다. 그 이유는 for문을 2부터 증가시키면서 매번 lcm을 찾아 계산해주었기 때문이다. 이제 생각을 바꿔 반복문의 수를 줄여야 한다. 

다음의 값을 x1에 대해 정리해 왼쪽으로 이동시킨다. (x1  >= b / a) 이러면 x1은 다음값을 만족시키는 가장 작은 정수가 된다. 따라서 x1 = b / a + 1의 값이 분자가 1이면서 가장 큰 단위분수를 구한것이다. 이 과정을 a가 1이 될때까지 반복한다. 

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>

int gcd(int a, int b)
{
    while(b!=0)
    {
        int c = a % b;
        
        a = b;
        b = c;
    }
    return a;
}


int lcm(int a, int b)
{
    return a * b / gcd(a, b);
    
}
int main()
{
    
    int t;
    scanf("%d", &t);
    
    while(t--)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        while(a != 1)
        {
            int x = b / a + 1;
            int denominator = lcm(b, x); //분모
            int frac1 = denominator / x; // 분자에 곱해줄 값.
            int frac2 = denominator / b; // 분자에 곱해줄 값.
            
            a = a * frac2 - frac1;//분모의 값을 맞춰주고 분자값 계산
            b = denominator;
            
            int check = gcd(a, b);
            if(check != 1) // 약분을 해주어야 하는지.
            {
                a = a / check;
                b = b / check;
                
            }
        }
        printf("%d\n", b);
    }
}