지원 물품 상자 계산

문제

사내 IT 지원 담당자는 새로 배치되는 업무용 컴퓨터에 연결선을 하나씩 지급한다. 이번에 연결선을 받아야 하는 컴퓨터는 모두 N대이며, 각 컴퓨터에는 정확히 한 개의 연결선이 필요하다. 담당자는 창고에 보관된 연결선을 먼저 사용하고, 부족한 수량만 새 물품으로 채우려고 한다. 창고에는 바로 사용할 수 있는 연결선이 S개 있다. 새 연결선은 한 상자에 K개씩 들어 있으며, 상자를 열어 일부만 구매할 수는 없다. 따라서 새 연결선을 구매할 때는 반드시 상자 단위로 구매해야 한다. 각 상자의 가격은 P원으로 모두 같고, 배송비나 다른 비용은 없다. 담당자는 모든 컴퓨터에 연결선을 지급할 수 있는 구매 방법 중에서 구매하는 상자 수가 가장 적은 방법을 선택한다. 예를 들어 필요한 연결선이 19개이고 창고에 8개가 있다면 추가로 11개가 필요하다. 한 상자에 5개가 들어 있을 때 두 상자로는 부족하므로 세 상자를 구매해야 한다. 세 상자에서 얻은 연결선과 창고 물품을 합친 뒤 19개를 지급하면 4개가 남는다. 남은 연결선은 버리지 않고 다시 창고에 보관한다. 창고에 있는 수량만으로 충분하면 상자를 하나도 구매하지 않는다. 이때 구매 비용은 0원이며, 지급하고 남은 창고 물품의 수를 그대로 계산한다. 구매한 상자의 연결선과 기존 연결선은 구별하지 않으며, 어느 것을 먼저 지급하는지는 결과에 영향을 주지 않는다. 사용할 수 없는 연결선이나 지급 도중 추가되는 컴퓨터는 없다. N, S, K, P가 주어질 때 최소로 구매할 상자 수, 총 구매 비용, 모든 컴퓨터에 지급한 뒤 남는 연결선 수를 구하는 프로그램을 작성한다. 최소 상자 수를 정하면 나머지 두 값도 하나로 정해진다.

입력

첫째 줄에 정수 N, S, K, P가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ S ≤ 1,000, 1 ≤ K ≤ 1,000, 1 ≤ P ≤ 1,000이다.

출력

최소 구매 상자 수, 총 구매 비용, 지급 후 남는 연결선 수를 이 순서대로 공백으로 구분하여 한 줄에 정수로 출력한다. 구매할 필요가 없으면 앞의 두 값은 모두 0이다.

19 8 5 230

3 690 4

12 17 4 900

0 0 5

24 6 9 140

2 280 0

출처: Devin.KR 자체 제작