백준 3343번 장미

문제 링크

디미고 정올 대비반이 끝나고 골랜디하면서 흥미로운 문제를 찾아서 블로그에 쓴다.

난 이 문제를 풀지 못했는데 k_san이 풀어서 풀이 물어보고 이해한 내용이다. 웰논이라는데 테크닉 이름은 모르겠다.

$A, B, C, D$는 헷갈리니까 $N_1, C_1, N_2, C_2$라고 하자.

$1$번을 $N_2$개 사고 $2$번을 $N_1$개 산다고 해보다. 그러면 $N_1 \cdot N_2$개를 사고 비용은 각각 $N_2 \cdot C_1, N_1 \cdot C_2$이다. 그러면 $\left\lfloor \frac{N}{N_1 \cdot N_2} \right\rfloor$개에 대해서는 $min(N_2 \cdot C_1, N_1 \cdot C_2)$을 사용한다. 남은 $( N \bmod (N_1 \times N_2) )$개는 브루트포싱을 통해 해결한다.

남은 개수를 $C$라고 하자. $C$의 상한은 $N_1 \cdot N_2$이다. 일반성을 잃지 않고 $1$번을 $2$번보다 더 조금금 썼다고 하자. 그러면 $1$번은 최대 $\sqrt{C}$이다. 왜냐면 $1$번은 $\sqrt{C}$보다 더 많이 썼다면 $2$번 또한 $\sqrt{C}$보다 더 많이 쓴다. 그러면 남은 개수보다 더 많이 사게 된다.

그래서 $1$번이 더 적다고 가정하고 $10^5$까지 $2$번이 더 적다고 가정하고 $10^5$까지 모두 돌려본 뒤 최솟값을 구하면 된다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll com1(ll n, ll a, ll b, ll c, ll d)
{
    ll ret = 1e18;
    for(ll i = 0; i < 100000; i++) {
        ll m = n - a * i;
        ll j = (m + c - 1) / c;
        ret = min(ret, max(b*i, 0LL)+max(d*j, 0LL));
    }
    return ret;
}

int main()
{
    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    ll ans = min({com1(N, A, B, C, D), com1(N, C, D, A, B)});
    cout << ans;
}