백준(BOJ) 10253 헨리(Python)

문제 내용.

 

단순 구현 문제.

a와 b를 입력받았을 때 a와 b를 수정하며 1/x <= a/b인 최소 x를 계속해서 구해나가면 된다.

1/x <= a/b는 b <= a*x로 변형하고, x를 변화시키며 while문을 이용해 조건에 맞는 값을 구했다.

이때 구해지는 x는 반드시 증가할 수밖에 없기 때문에 x는 처음에 한 번만 초기화해주면 된다.

그렇게 구한 x를 이용하면 다음 a와 b는 a=a*x-b, b=b*x로 구할 수 있다.

그러나 이는 a와 b의 약분을 고려하지 않은 값이기 때문에 b가 매우 커질 수 있어 최대공약수로 둘을 약분해줘야 한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)
for _ in range(int(input())):
    a,b=map(int,input().split())
    x=1
    while a!=1:
        while b>a*x:
            x+=1
        a=a*x-b
        b=b*x
        k=math.gcd(a,b)
        a=a//k
        b=b//k
    print(b)

 

처음에는 약분을 안 해줘서 TLE를 받았다.

꼼꼼하게 생각했어야 하는데,,