백준 1214번: 쿨한 물건 구매 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

쿨한 물건 구매
브루트포스 최적화 문제입니다.

풀이

일반성을 잃지 않고 $P \geq Q$라 합시다.
$Px + Qy \geq D\ (x, y > 0)$을 만족하는 $Px + Qy$의 최솟값을 찾으려고 합니다.
이는 $x$를 정하면 $y$도 자동으로 정해집니다.

$Px \leq D$인 경우 $(Px - D) \bmod Q$로 $Px + Qy - D$를 구할 수 있습니다.
여기서 나머지 연산을 하는 것은 값이 양수가 될 때 까지 $Q$를 더하는 것으로 해석할 수 있습니다.

$Px > D$인 경우 $y = 0$입니다.
아까와 같은 원리로 $-D \bmod P$로 $Px - D$를 구할 수 있습니다.
그 다음 $Px < D$를 만족하는 $x$를 살펴보면 시간 복잡도는 $O\left(\dfrac{D}{P}\right)$입니다.

그런데 $x \geq Q$인 경우는 살펴볼 필요가 없습니다. 왜냐하면 $Px = P(a + Q)$ 꼴로 변형하면 $Q$로 나타낼 수 있기 때문입니다.
따라서 $Px < \min(D, PQ)$에 대해서만 살펴보면 됩니다.

시간 복잡도는 $O\left(\dfrac{\min(D, PQ)}{P}\right) = O\left(\min\left(\dfrac{D}{P}, Q\right)\right)$입니다.

$P \geq Q$라 했으므로 시간 복잡도의 상한은 $O\left(\min\left(\dfrac{D}{P}, P\right)\right)$입니다.
$P \geq \sqrt D$ 인 경우 $\dfrac{D}{P} \leq \sqrt D$이므로 $O(\sqrt D)$입니다.
$P < \sqrt D$ 인 경우 $\min$에 의하여 $O(\sqrt D)$입니다.

따라서 실제 시간 복잡도는 $O(\sqrt D)$가 되며, 시간 내에 통과할 수 있습니다.

코드

C++에서는 음수 나머지 연산의 반환값이 음수이므로 $a \equiv a + m \pmod m$를 이용해 제수를 더해서 양수로 만들었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll d, p, q;
    cin >> d >> p >> q;

    if (p < q)
        swap(p, q);

    ll limit = min(d, p * q);

    ll answer = d + (-d % p + p) % p;
    for (ll i = 0; i < limit; i += p) {
        answer = min(answer, d + ((i - d) % q + q) % q);
    }

    cout << answer;
}

백준 1214번: 쿨한 물건 구매 [C++]