티스토리 뷰

Coding Test/알고스팟

[C++] 알고스팟/유클리드 - 마법의 약

Junchoi 2020. 1. 8. 01:27

문제링크

https://algospot.com/judge/problem/read/POTION

 

algospot.com :: POTION

마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 해르미온느가 재빨리 레시피의 정확한 양을 알려주어서 약을 전부 망치는 것은 면했습니다. 지금 얼른 재료를 더 넣어서 약을 완성해야 합니다. 이번 시간에 만드는 마법의 약은 n 종류의 재료를 각 ri 숟가락씩 넣어서 만들어야 합니다. 모든 재료를 정확히 넣었을 경우 만

algospot.com

 

이미 냄비에 넣어버린 재료에서 레시피의 재료 비율에 맞게 넣으려면 필요한 양에 비해 이미 넣어버린 양의 비율이 가장 높은 값만큼 모든 재료에 적용해야 합니다. 아래의 값에서 가장 큰 값은 7/4이니까 다른 재료들은 최소한 7/4 만큼은 넣어줘야합니다. 

하지만 X를 모든 레시피에 곱했을 때 정수가 되어야 하는데 7/4를 곱하면 정수가 나오지 않습니다.

그렇기 때문에 실제로 레시피에 곱해야 하는 수는 X 이상의 유리수입니다. 따라서 X보다 더큰 유리수 Y는 a/b라고 쓸 수 있습니다.

모든 재료에 대해 Y를 곱했을 때 나오는 값이 정수인 최소의 Y를 찾기 위해서는 recipe[i] * (a/b) 에서 b는 모든 레시피의 최대 공약수가 되어야 합니다.

최대 공약수 b를 구하고나면 1/b를 계속 더해나가면서 Y를 찾을 수 있습니다.

 

구현 코드

 

'Coding Test > 알고스팟' 카테고리의 다른 글

[C++] 알고스팟/완전탐색 - 게임판 덮기  (0) 2020.01.11
[C++] 알고스팟/완전탐색 - 소풍  (0) 2020.01.10
[C++] 알고스팟/에라토스테네스의 체 - 비밀번호486  (0) 2020.01.06
[C++] 알고스팟/삼분검색 - 꽃가루 화석  (0) 2020.01.05
[C++] 알고스팟/이분법 - 승률 올리기  (0) 2020.01.05