====== 쿨한 물건 구매 ======

===== 풀이 =====
  * P원 지폐를 x개 사용했을때 만들수 있는 최소 금액을 각각 구한다음에 그중에서 최솟값을 찾으면 된다.
  * 탐색해야 하는 x의 범위를 줄이는 것이 핵심이다.
    * x가 Q보다 클 경우는 확인할 필요가 없다. P원 지폐를 Q개 쓴것은 Q원 지폐를 P개 써서 만들수 있기 때문에, P를 (Q+a)개 사용해서 만들수 있는 값은 P를 a개 사용해서 똑같이 만들 수 있다
      * 엄밀하게 하면 Q/gcd(P,Q)개 까지만 확인하면 된다 
    * P*x가 D보다 커지면 당연히 확인할 필요가 없다.
  * 따라서 x < min(D/P, Q) 까지만 확인하면 된다. P≥Q 가 되도록 한다면, min(D/P, Q) ≤ min(D/P, P) ≤ sqrt(D) 이니까, 총 시간복잡도도 O(sqrt(D))가 된다.
  * 사실 이것과 관련해서는 [[ps:여러가지 수학 정리#프로베니우스의 동전 문제]]를 참고하면, gcd(P,Q)=g라고 할때 g(P/g-1)(Q/g-1) 이상의 g의 배수는 모두 만들수 있으므로, D>=g(P/g-1)(Q/g-1) 일때는 그냥 D보다 크거나 같은 최소의 g의 배수를 출력하면 된다.
    * 하지만 D가 저 값보다 작을때에는 어차피 똑같이 루프를 D/P 번 돌려야 한다. D<g(P/g-1)(Q/g-1) = O(PQ) 라고 놓고 구하면, D/P = O(sqrt(D))라서 시간 복잡도는 어차피 똑같다.




===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1214. 쿨한 물건 구매".

- Problem link: https://www.acmicpc.net/problem/1214
- Solution link: http://www.teferi.net/ps/problems/boj/1214
"""


def main():
    D, P, Q = [int(x) for x in input().split()]
    if Q > P:
        P, Q = Q, P
    min_cost = (D + P - 1) // P * P
    for p_cost in range(0, min(D + 1, P * Q), P):
        cost = p_cost + (D - p_cost + Q - 1) // Q * Q
        min_cost = min(min_cost, cost)
    print(min_cost)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}