[BOJ] 백준 3343번: 장미

1일 1PS 13일차!

📚 문제

---

골드 4

• 최소공배수 lcm 의 개수까지는 무조건 가성비 좋은 꽃집에서 사는 것이 이득이다.
• 즉 가성비 안좋은 꽃집에서는 최소공배수 lcm 개수까지는 절대 구매하지 않는다.

💡 포인트

---

1. 가성비가 좋은 꽃을 구분한다.
2. 가성비가 안좋은 꽃을 구매할 최대 개수는 lcm // c 개 이다.
3. 가성비가 안좋은 꽃의 개수를 하나씩 사면서 최소 cost 를 구한다.
4. 이때 가성비 안좋은 꽃으로 모두 구매한 경우 loop 를 중지한다.

💻 코드

---

import math

n, a, b, c, d = map(int, input().split())

# a,b 가 가성비가 좋은 쪽
if b * c > d * a:
    a, b, c, d = c, d, a, b

lim = math.lcm(a, c) // c

min_cost = math.ceil(n / a) * b

for i in range(1, lim + 1):
    tmp = n - i * c
    if tmp < 0:
        min_cost = min(min_cost, i * d)
        break
    min_cost = min(min_cost, math.ceil(tmp / a) * b + i * d)

print(min_cost)