[Python/파이썬] 백준 3343번 장미

3343번: 장미

 

문제

상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다.

첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격이 저렴하면, N개 보다 많이 구매한 다음 남은 장미는 꽃집 점원에게 줄 것이다.

상근이가 장미를 적어도 N개 구매하는데 필요한 최소 금액을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, A, B, C, D가 주어진다. N은 $10^{15}$를 넘지 않으며, A, B, C, D는 $10^5$를 넘지 않는다.

출력

첫째 줄에 장미를 적어도 N개 사는데 필요한 돈의 최솟값을 출력한다. 정답은 항상 $10^{18}$을 넘지 않는다.

코드

from math import ceil
import sys
input = sys.stdin.readline

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

if b/a < d/c:   # cd의 가성비가 더 안 좋다면 ab와 cd 바꾸기
    a, b, c, d = c, d, a, b

ans = sys.maxsize
for i in range(c):  # ab 개수
    c_num = ceil((n-i*a)/c)
    if c_num < 0:
        c_num = 0
    ans = min(ans, i*b+c_num*d)
    if c_num == 0:
        break
print(ans)

가성비가 좋지 않은 꽃집에서 가성비가 좋은 꽃집의 한 다발의 꽃 개수보다 적은 다발을 사면 된다.

 

무조건 A개 B원에 파는 꽃집(ab)이 C개 D원에 파는 꽃집(cd)보다 가성비가 안 좋다고 하기 위해 cd의 가성비가 더 안 좋은 경우 ab와 바꿔주었다.

 

이제 가성비가 안 좋은 다발인 ab를 c개 미만까지 사면서 N개를 사는데 드는 비용의 최소값을 구한다. 이때 cd가 더 가성비 좋은 다발인데 cd를 사지 않고 ab로 모두 사면 총 가격이 더 비싸질 것은 자명하다. 그렇기 때문에 cd 다발의 개수인 c_num이 0 이하가 되면 break한다.