[c++] 백준 10253 - 헨리(분수를 gcd로 나눠주자)

0. [c++] 백준  -

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

1. 풀이

1) 음... 이 문제를 풀면서 어려웠던 부분은 시간 초과를 해결하는 부분이었다.

처음에는 i를 1씩 증가시키면서 그에 따라서 a,b가 커지고, 정답을 구해내는 방식으로 코드를 구현하였는데, 그렇게 하면 반복이 많아져서 시간초과를 하게되고, 또한, 정확한 답을 구해내지도 못하였던 것이었다.

2) 따라서 이러한 문제를 해결하기 위해서, 바로 다음 값을 구해내는 방식을 선택하였다.

우선, i의 다음값의 기준을 생각해보자. 이러한 값을 성립시키면되는데, 이러한 i를 만들어주는 식을 구현하고, 

이후 과정은 밑의 코드와 같이 진행되면 된다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream>   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;     std::cin >> T;     while (T--) {         std::cin >> a >> b;         std::cout << calc(a, b) << std::endl;     } } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!