BOJ 3343 - 장미

BOJ 3343 - 장미

$a$ 집의 개수 $N_a$와 가격 $C_a$, $b$집의 개수 $N_b$와 가격 $C_b$ 라 하자.

$a$ 집의 꽃을 사는 묶음 수를 $u$ , $b$ 집의 꽃을 사는 묶음 수를 $v$라 하자.

$N \le N_a \cdot u+N_b \cdot v$ 그리고 총 가격은

$$ C=C_a \cdot u+C_b \cdot v $$

위 부등식을 $v$에 대해 나타내면

$$ \dfrac {N-N_a \cdot u}{N_b} \le v $$

이므로 $u$가 정해지면 $v$는 $v \ge \left\lceil \dfrac {N-N_a \cdot u}{N_b} \right\rceil=\left\lfloor \dfrac {N-N_a \cdot u+N_b-1}{N_b} \right\rfloor$ 여야 한다.

이제 $a$가 항상 더 가성비가 안좋다고 해보자.

$LCM(N_a,N_b)$ 를 봤을 때, 이 만큼의 그룹은 항상 더 가성비가 좋은 $b$로 사는게 이득이다.

그럼 $a$를 최대 $N_b-1$개 까지 사는것만 확인하고 나머지는 $b$로 채워주는것이 항상 최적이다.

$a$를 $N_b$개 사버리면 그건 그냥 $b$를 $N_a$ 개 사는게 더 이득이라 항상 손해기 때문이다.

$N_b \le 10^5$이므로 브루트포스로 이 문제를 해결할 수 있다.

void solve() {  
   int n;  
   // <개수, 가격>  
   pi a, b;  
   cin >> n >> a.fi >> a.se >> b.fi >> b.se;  
  
   auto get_v = [&](int u) {  
      return max(0ll, (n - a.fi * u + b.fi - 1) / b.fi);  
   };  
   auto get_cost = [&](int u) {  
      int v = get_v(u);  
      return u * a.se + v * b.se;  
   };  
  
   int ans = 2e18;  
   for (int u = 0; u <= min((n + a.fi - 1) / a.fi, 999999ll); u++) ans = min(ans, get_cost(u));  
   swap(a, b);  
   for (int u = 0; u <= min((n + a.fi - 1) / a.fi, 999999ll); u++) ans = min(ans, get_cost(u));  
   cout << ans;  
}