백준 10253번 헨리

🔒문제 url

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

🔑알고리즘

풀이과정은 크게 두 단계로 나뉜다.

1. $\frac{a}{b} \ge \frac{1}{x}$ 를 만족하는 $x$의 최소값을 찾는다.
2. $\frac{a}{b} - \frac{1}{x}$ 연산 결과를 약분한다.

위 과정을 $a = 1$이 될 때까지 반복한 후, b를 출력한 것이 정답이 된다.

1번 식을 전개하면 $x \ge \frac{b}{a}$ 가 되고,
이를 만족하는 최소값 정수 $x$는 int(b/a) + 1이 됨을 알 수 있다.

이후 2번 과정을 진행하는데, 우선 1번을 통해 구한 $x$를 통해 뺄셈 연산을 한다.

$\frac{a}{b} - \frac{1}{x} = \frac{a \times x}{b\times x} - \frac{b}{b \times x} = \frac{a\times x - b}{b\times x}$

이후, 위 연산 결과를 약분하기 위해 GCD를 활용한다.

위 과정을 분자가 1이 될 때까지 반복한다.

🐾부분 코드

cin >> a >> b;
while (a > 1)
{
    // (a/b) >= (1/x) 만족
    int x = b / a + 1;
    a = a * x - b;
    b *= x;

    int gcd = GCD(a, b);
    a /= gcd, b /= gcd;
}

<풀이과정 반복>
1, 2번 과정을 분자가 1이 될 때까지 반복한다.

int GCD(int a, int b)
{
    while (b)
    {
        int mod = a % b;
        a = b;
        b = mod;
    }
    return a;
}

<GCD 함수>
최대공약수를 구하기 위한 알고리즘이다.
본 포스팅에서 해당 알고리즘 설명은 생략한다.

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

int t;

void INPUT()
{
    IAMFAST
    cin >> t;
}

int GCD(int a, int b)
{
    while (b)
    {
        int mod = a % b;
        a = b;
        b = mod;
    }
    return a;
}

void solution()
{
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        while (a > 1)
        {
            // (a/b) >= (1/x) 만족
            int x = b / a + 1;
            a = a * x - b;
            b *= x;

            int gcd = GCD(a, b);
            a /= gcd, b /= gcd;
        }
        cout << b << '\n';
    }
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

2023 ICPC 예선에 앞서, KAUPC 이후 문외한이었던 PS 감을 올리는 중이다.
실버 상위만 돼도 시간이 오래 걸리는 건 물론 못 푸는 문제도 있어 정말 큰일이다. 어쩌면 좋아🥳