티스토리 뷰

ICPC/2014 인터넷예선

D. 헨리

전명우 2014. 10. 7. 18:31

문제에서 주어진 방법대로, 분수 $\frac{a}{b} (a < b)$ 를 단위 분수의 합으로 나타냈을 때 마지막 단위 분수의 분모를 구하는 문제다.


문제 입력 형식의 마지막 조건에 따라 $\frac{a}{b}$ 를 구성하는 단위 분수는 31개 미만이다. 이제 문제에서 중요한 것은 $\frac{a}{b} \geq \frac{1}{x}$ 를 만족하는 최소 x 를 구하는 것이다. 이분 검색을 통해서 구해도 되고, 직접 계산을 통해 구해도 된다. 매번 이를 계산하면서 마지막 분수를 구하면 된다.



'ICPC > 2014 인터넷예선' 카테고리의 다른 글

G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
C. 그리드 그래프  (2) 2014.10.07
B. Driving License  (1) 2014.10.07
A. ACM 호텔  (0) 2014.10.07
댓글
댓글쓰기 폼