본문 바로가기

알고리즘/백준[C++]

[백준] 10253_헨리_C++

728x90
반응형

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

 

10253번: 헨리

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기

www.acmicpc.net

 

 

풀이

문제가 엄청 복잡하게 쓰여져있는데 일단 시키는대로 하면 풀리는 문제였습니다.

라고생각했지만 시간초과가 뜨더군요.

최대 공약수를 사용한 분수계산식으로 변경하여 해결하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <cmath>

using namespace std;

int t, a, b;
int answer;

int gcd(int a, int b) {
    return a % b ? gcd(b, a % b) : b;
}

int calc(int a, int b) {
    int i = 1, GCD;
    while (a != 1) {
        i = (b % a == 0) ? (b / a) : (b / a + 1);
        a = a * i - b;
        b = b * i;
        // 분수식을 좀더 단순화
        GCD = gcd(a, b); 
        a /= GCD; 
        b /= GCD;
    }
    return b;
}

int main() {
    int T, a, b;
    cin >> T;
    while (T--) {
        cin >> a >> b;
        cout << calc(a, b) << endl;
    }
}

 

728x90
반응형

'알고리즘 > 백준[C++]' 카테고리의 다른 글