양팔 저울 timer 1s memory - MB

과학자 관영이는 양팔저울을 이용하여 실험재료를 측정할 때 단지 두 종류의 추만을 사용한다. 예를 들어 실험재료 200그램을 측정할 때 300그램 추와 700그램 추만을 사용한다고 하자. 이때 아래 그림1 과 같이 300그램 추 3개와 700그램 추 1개를 이용하여 잴 수 있다. 그림2와 같이 300그램 추 4개와 700그램 추 2개를 이용할 수도 있지만 추를 더 많이 사용하므로 효율성을 따지는 관영이는 그렇게 하지는 않는다. 두 추 의 무게 A, B(A!=B, 1 ≤ A, B ≤ 10,000)그램과 측정하고자 하는 실험재료의 무게 D( 1≤ D ≤ 50,000)그램이 주어질 때, 실험재료 D그램을 가장 효율적으로 측정하고자 한다. 이 때 필요한 추 A의 개수와 B의 개수를 구하는 프로그램을 작성하시오. 입력되는 데이터는 반드시 답이 존재한다.

효율적이라 함은 아래와 같다. 1. 실험재료 D그램을 측정할 때 추 A, B의 개수는 충분히 있다. 2. 사용되는 A그램 추의 개수를 x, B그램 추의 개수를 y라고 할 때, (x + y)가 최소가 되어야 한다. 3. 위와 같은 경우가 2가지 이상 발생할 경우(Ax + By)가 최소가 되어야 한다.