boj 1214 : 쿨한 물건 구매

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

1214번: 쿨한 물건 구매

 

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}$ 가 되어 유효한 시간 안에 답을 구할 수 있다.

 

코드