[백준/1214] 쿨한 물건 구매 (Python)

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

1214번: 쿨한 물건 구매

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:49:07

 

---

 

문제 설명

 

 

구사과는 지폐를 오직 두 종류만 가지고 있다. 바로 P원 지폐와 Q원 지폐이다. 이 두 종류의 지폐를 구사과는 무한대만큼 가지고 있다.

오늘 구사과가 구매하려고 하는 물건의 가격은 D원이다. 구사과가 이 물건을 구매하기 위해서 지불해야 하는 금액의 최솟값은 얼마일까?

물건을 구매하기 위해서는 물건의 가격보다 크거나 같은 금액을 지불해야 한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 D, P, Q가 주어진다. 모두 109보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 물건을 구매하기 위해 구사과가 지불해야 하는 금액의 최솟값을 출력한다.

 

입력 예시

 

17 7 13

 

출력 예시

 

20

 

 

---

 

풀이

 

 

우선 '이 문제를 어떻게 해결할 것인가' 대략적인 방향을 정해 보자. nP + mQ >= N 을 만족하는 최소 정수 nP + mQ를 찾는 것이고, P, Q, N의 값은 10^9 이하이다. 즉 우리는 이를 만족하는 조합 (n, m)을 찾아내야 한다. n을 고정한다면, 최소 정수 조건에 부합하는 m이 자동으로 계산된다(나눗셈 몫과 나머지로 판별 가능하다). 또한 검색 범위는 nP <= D일때를 기준으로 검색해볼 수 있겠다. 따라서 O(N / P)의 시간복잡도로 브루트포스를 이용해서 풀이할 수 있다. P값이 클수록 시간복잡도가 줄어드므로 필요에 따라 P, Q의 위치를 바꿀 수 있다.

 

문제는 극단적인 케이스. 이를테면 N = 10^9, P = 3, Q = 2인 경우를 생각해 보자. 이 때의 연산 횟수는 약 3.33*10^9이 되므로, 0.5초의 빠듯한 시간복잡도 내에는 정상적인 풀이가 불가능하다. 즉 다른 테크닉이 적용될 필요가 있다.

 

여기서 잠깐. (n, m)을 탐색할 때, n값에 따른 주기성이 발견된다면 그 주기만을 탐색해 볼 수 있지 않을까? 라는 생각을 해볼 수 있다. n'P + m'Q = nP + mQ를 만족하는 (n', m')가 존재한다고 가정하자. ( n < n', m > m')

 

P, Q의 최소공배수 lcm(P, Q) = R이라고 했을 때, 위 수식은 다음과 같이 변형될 수 있다. 

 

nP + mQ = nP + kR + mQ - kR (k >= 1)

= (nP + k(R / P) P) + (mQ - k(R / Q) Q)

= (n + k(R/P)) P + (m - k(R/Q))Q

= n'P + m'Q

 

따라서 n' = n + k (R/P), m' = m + k (R/Q) 가 만족되고, R / P, R / Q 모두 정수임이 보장된다. 즉 n을 기준으로  R/P 주기로 값이 반복됨이 성립한다! 즉 탐색 범위는 R까지로 줄어들 수 있으며, 이 경우 탐색의 시간복잡도는 O( min(N, R) / P ) 로 줄일 수 있다! (최소공배수가 N을 넘는 경우를 고려하자) 대부분의 경우 시간복잡도가 기존에 비해 매우 줄어듬을 알 수 있다.

 

풀이 코드

def gcd(a, b) :
  while b :
    a, b = b, a % b
  return a

def lcm(a, b) :
  return a // gcd(a, b) * b

D, P, Q = map(int, input().split())
if P < Q :
  P, Q = Q, P
  
ans = float('inf')
q = [0]

for i in range(0, min(D, lcm(P, Q))+P, P) :
  target = max(D - i, 0)
  tmp = target // Q * Q
  if tmp < target :
    tmp += Q
  if ans > tmp + i :
    ans = tmp + i

print(ans)

풀이 완료!