boj 1214 : 쿨한 물건 구매
https://www.acmicpc.net/problem/1214
1214번: 쿨한 물건 구매
첫째 줄에 D, P, Q가 주어진다. 모두 109보다 작거나 같은 자연수이다.
www.acmicpc.net
D, P, Q가 각각 $10^9$이하의 자연수일 때,
D <= aP + bQ 를 만족하는 aP + bQ 의 최소값을 찾는 문제이다.
가장 간단한 풀이로는,
aP <= D + P를 만족하는 모든 a값에 대하여, D <= aP + bQ를 만족하는 aP + bQ의 최소값을 구하는 방법이 있다.
물론 이 방법은 a의 범위가 0~$10^9$이므로 time out 이다.
시간초과가 나지 않는 풀이를 찾아야한다.
[1] D <= aP + bQ
[2] D <= xPQ + a'P + b'Q (a' < Q, b' < P)
[3] a'P + b'Q < 2PQ
[4] D - xPQ <= a'P + b'Q
[1] 의 식을 (a' < Q, b' < P) 조건을 만족하도록 [2]와 같이 수정한다.
-> aP는 (PQ의 배수 + a'P) 와 같이 나타낼 수 있으므로, [2]와 같이 변환이 가능하다.
[2] 에서 a' < Q, b' < P 이므로, [3]의 식을 만족한다.
[4] 에서 D - xPQ가 PQ이상, 2PQ 미만이 되도록 정한다.
이제, D - xPQ = D' <= a'P + b'Q (D' < 2PQ)를 만족하는 a', b'을 각각 찾으면 된다.
a' 의 범위가 (0 ~ Q-1) 이다.
D' <= a'P + b'Q <= $10^9$ 이므로, P > Q로 두었을 때 a'의 범위는 0~$\sqrt{10^9}$ 가 되어 유효한 시간 안에 답을 구할 수 있다.