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++]' 카테고리의 다른 글
[백준] 1141_접두사_c++ (0) | 2022.07.27 |
---|---|
[백준] 괄호제거_2800_C++ (0) | 2022.07.27 |
[백준] 크로아티아 알파벳 C++ (0) | 2021.05.07 |
[백준] 단지번호붙이기 C++ (0) | 2021.04.29 |
[백준 11048] 이동하기 (0) | 2020.07.31 |