# [Gold III] 장미 [문제 링크](https://www.acmicpc.net/problem/3343) ## 문제 설명 <p>상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다.</p> <p>첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격이 저렴하면, N개 보다 많이 구매한 다음 남은 장미는 꽃집 점원에게 줄 것이다.</p> <p>상근이가 장미를 적어도 N개 구매하는데 필요한 최소 금액을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 N, A, B, C, D가 주어진다. N은 10¹⁵를 넘지 않으며, A, B, C, D는 10⁵를 넘지 않는다.</p> ## 출력 <p>첫째 줄에 장미를 적어도 N개 사는데 필요한 돈의 최솟값을 출력한다. 정답은 항상 10¹⁸을 넘지 않는다.</p> ## 풀이 #### ac * k (k는 0 이상의 정수) 번의 공통 연산을 제외하면 최대 a를 c번 or c를 a번 연산만 남아 브루트포스로 해결할 수 있다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, a, b, c, d; cin >> n >> a >> b >> c >> d; // ac * k번의 공통 연산을 빼면 나머지 연산은 항상 ac번보다 작음 ll minPrice=LLONG_MAX; for(ll extraA=0;extraA<=c && extraA*a<=n;extraA++) { // a를 extraA번 minPrice = min(minPrice, extraA*b + (n-extraA*a+c-1)/c*d); } for(ll extraC=0;extraC<=a && extraC*c<=n;extraC++) { // c를 extraC번 minPrice = min(minPrice, (n-extraC*c+a-1)/a*b + extraC*d); } cout << minPrice; } ```