[백준(BOJ)] 헨리(10253번)_C++

생각보다 어려운 문제였다.

 

처음엔 그냥 x를 1씩 늘려가며 답을 구했다.

역시나 시간초과가 발생했고, 몇가지 테스트를 통해 최대공약수를 활용해야함을 알아냈댜.

그래도 시간초과는 발생했다. 내가 생각하기에는 x를 1씩 늘리는 것 때문이었다.

수식을 잘보면 x >= b/a 임을 도출해낼 수 있다.

이를 이용해 for문을 이용하지 않고 단번에 x를 구할 수 있다.

 

시간초과를 해결했더니 갑자기 DivisionByZero 런타임에러가 발생했다.

엄청난 삽질 끝에 while문의 탈출 조건을 한박자 늦게 넣었다는 것을 깨달았다.

탈출조건은 while문 가장 앞단에 넣어야 temp_a가 0이 되는 상황을 피할 수 있었다.

 

해결방법들은 간단했지만 삽질을 꽤나 했던 힘든 문제였다.

 

---

정답 코드

#include <iostream>

using namespace std;

int T, a, b;

int GCD(int a, int b){
    int tmp, n;
 
    if(a < b){
        tmp = a;
        a = b;
        b = tmp;
    }

    while(b != 0){
        n = a % b;
        a = b;
        b = n;
    }

    return a;
}


int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> T;

    //test data
    while (T--){
        cin >> a >> b;

        int temp_a = a;
        int temp_b = b;
        int x = 1;

        //henry's algorithm
        while(1){

            //output
            if (temp_a == 1){
                cout << temp_b << "\n";
                break;
            }

            if (temp_b % temp_a == 0)
                x = temp_b / temp_a;
            else
                x = temp_b / temp_a + 1;

            temp_a = temp_a * x - temp_b;
            temp_b = temp_b * x;

            int gcd = GCD(temp_a, temp_b);
            temp_a /= gcd;
            temp_b /= gcd;
        }
    }
}