BOJ-10253 헨리

Seok·2020년 12월 14일
0

Algorithm

목록 보기
58/60
post-thumbnail

접근

  • 방정식과 시간복잡도에 대한 고려를 해야하는 문제였다.

  • 먼저 헨리식 표현법의 첫번째 수를 구하는 방법은 아래와 같다.

  • 1x1ab\frac{1}{x^{1}} \leq \frac{a}{b} 을 만족하는 최대의 x1x^1ba의 값은 알고있으므로 x1x^1에 2부터 값을 대입하여 쭉 올라가면 정답을 찾을 수 있을 것이다. 하지만 이는 시간초과를 받게된다.

  • 따라서 2부터 값을 대입하는 부분을 O(n)O(n)에서 O(1)O(1)로 줄여야했다.

  • 식을 정리하여 b/ax1b/a \leq x^1이렇게 나타내면 O(1)O(1) 만에 x1x^1을 알 수 있고, ab의 배수가 아닌경우를 고려하여 값에 +1을 해주어야한다.

  • x1x^1을 구한후 a,b에 각각 값을 갱신해주고 a가 1이 될때 까지 반복하면 된다.

  • 57=12+??\frac{5}{7} = \frac{1}{2} +\frac{?}{?}라는 식을 구하고 통분을 하면 ax1+bbx1\frac{a \cdot x^1+b}{b \cdot x^1}라는 식을 얻을 수 있고, a=ax1+ba=a \cdot x^1+b, b=bx1b=b \cdot x^1을 대입하여 과정을 반복한다.

  • 이때 ab가 기약분수 꼴이 아닌 결과가 나올때도 있는데, 이 문제는 gcd(a,b)를 각a,b에 나눠주면서 해결할 수 있었다.

코드(C++)

#include <iostream>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
typedef long long ll;
ll t,a,b;
ll gcd(ll a,ll b){ return b ? gcd(b,a%b):a;}

int main(){
    FIO;
    cin>>t;
    while(t--){
        cin>>a>>b;
        while(a!=1){
            ll tmp = (b%a!=0) ? b/a+1:b/a;
            a = a*tmp-b; b *= tmp;
            ll res = gcd(a,b); a/=res; b/=res;
        }
        cout<<b<<"\n";
    }
    return 0;
}

결과

profile
🦉🦉🦉🦉🦉

0개의 댓글