20.06.26 개발일지 - Henry

https://www.acmicpc.net/problem/10253

10253번: 헨리

a / b 분수가 입력 되었을 때 x(i) = {x | a/b >= 1 / x 중 가장 큰 x}일 때 가장 마지막 x(i)를 출력하는 문제입니다.

 

처음에는 gcd와 lcm으로 연산을 하였으나, 시간이 너무 오래 걸렸습니다.

 

그 다음에 연산한 것은 a와 b의 각 차수 별 항에서 규칙성을 찾아서 적용하는 것입니다

min(i) = b(i) / a(i) + 1일 때, a(i + 1) = a(i) * min(i) - b(i), b(i + 1) = b(i) * min(i)를 적용하였습니다.

하지만 이 역시 시간 초과가 걸렸습니다.

 

솔직히 이보다 더 빠르게 만들 자신이 없었습니다.

입력을 c스타일 입력으로 바꾸기도 했으나, 여전히 문제가 해결되지 않았습니다.

 

그러다가 정답을 찾아 보는데, 어이 없는 문제점이 두개가 있었습니다.

 

하나는 반복문을 do-while이 아니라 그냥 while문으로 하는 것.

이렇게 되면 처음부터 분자가 1일 때는 자기 자신이 출력이 되는데 왜 성립하는지 몰랐습니다.

하지만 곧, 제가 문제를 잘못 읽었다는 것을 깨달았습니다.

이 문제는 자기 자신이 답이 될 수 있었습니다.

이 부분이 조금 뼈아팠습니다.

 

다른 하나의 문제는 연산이 다 끝나면 항상 gcd로 나누어 주는 것.

서로소를 곱하고 더하는데 최대공약수가 1보다 큰 경우가 발생을 하는가 싶었습니다.

이를 확인하기 위해 값을 최대로 올려보았더니, 곧바로 확인이 가능했습니다.

1에 근접하고 분모가 매우 큰 경우에는 종종 최대공약수가 1보다 큰 경우가 발생하기도 하였습니다.

 

문제의 해결법은 곧잘 찾아내지만, 아직은 세세하게 런타임을 줄이지는 못하는 것 같습니다.

매일 한문제씩 풀어나가면서 이런 실수를 최대한 줄이고, 문제 푸는 속도도 키우도록 하겠습니다.

#include <iostream>

using namespace std;

int GCD(const int& a, const int& b)
{
    return (b == 0) ? a : GCD(b, a % b);
}

int main()
{
    int testcase = 0, a = 0, b = 0, min = 0, gcd = 0;
    
    cin >> testcase;

    while (testcase-- > 0)
    {
        cin >> a >> b;        
        while (a != 1)
        {
            min = (b + a - 1) / a;
            a = a * min - b;
            b *= min;
            gcd = GCD(a, b);
            a /= gcd;
            b /= gcd;
        } 
        cout << b << endl;
    }

    return 0;
}