[BOJ] 1214번: 쿨한 물건 구매

https://www.acmicpc.net/problem/1214

주어진 P, Q에 대해 P를 0개 1개 썼을 때 D에 가장 근접한 값, 2개 썼을 때 D에 가장 근접한 값, .., Q-1개 썼을 때 D에 가장 근접한 값을 생각하면 그 안에 답이 있습니다.(P를 Q개 이상 쓸 경우에는 그냥 Q를 P개 씀으로서 대체 가능)

그런데 Q가 클 때 이것을 어떻게 시간 내에 구할지가 문제인데, 우선 P를 D/P + 1개 이상 쓴 경우는 고려할 필요가 없습니다. 즉 D = 100000이고 P, Q = 10000 10000 일 때에는 P를 최대 10000개까지 볼 필요 없이 10개까지만 쓴다고 생각해도 됩니다. 두 번째로 Q가 P보다 클 경우 둘을 바꿔줍니다. 즉 D = 10000000이고 P = 2, Q = 1000000 일 때 2를 0개, 1개, 2개, 3개, ..., 999999개 쓰는 것을 고려하는 대신 1000000을 0개, 1개 쓰는 경우만 고려하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/1214.cpp