BOJ 1214 : 쿨한 물건 구매

문제 링크 : https://www.acmicpc.net/problem/1214

사전 지식 / 관련 알고리즘 : 수학

 

Pa + Qb ≥ D 가 되어야 한다.

가장 먼저 드는 생각은, P 의 개수 a 를 0, 1, 2, ... 로 늘려가면서, 그에 맞는 b 의 최솟값을 찾는 것이다.

 

P의 개수 a 가 결정된다면, 

Qb ≥ D - Pa 이고, 이를 만족하는 자연수 b 의 최솟값은 ⌈ (D-Pa) / Q ⌉ 이다.

이를 깔끔하게 구하는 법은, 분자에 Q-1 을 더하고 나누는 것이다.

즉, ⌈ (D-Pa) / Q ⌉ 는 ceil 함수 없이 (D-Pa+Q-1) / Q 로 구할 수 있다.

 

하지만, 이러면 시간 초과가 날 수 있다.

만약 D = 10억, P = 2 라면,

a 의 범위는 0, 1, 2, ... 5억 까지도 가능하기 때문이다.

 

잘 생각해보면, P의 개수 a 는 Q 를 넘길 수 없다.

왜냐하면, a == Q 가 되는 순간, 즉 P 를 Q 개 쓴 순간은, 반대로 Q 를 P 개 쓴 순간으로 바꿀 수 있기 때문이다.

그러면 P 의 개수는 Q 개 → 0 개가 되어도 상관 없다는 것이다.

잘 이해가 안 가는 사람들은 아래 "더보기" 를 클릭하자.

P = 5, Q = 8 이라고 하자.

P 를 11 개 쓰는 것은 의미가 없다. 11 > Q 이기 때문이다.

 

P * 11

= P * 8 + P * 3

= P * Q + P * 3

= Q * P + P * 3 이다.

즉, Q 를 P 개 쓰고, P 개수를 11에서 3으로 줄인 상황과 완전히 똑같다.

 

따라서 P 를 11 개 쓴 상황은 P 를 3개 쓴 상황에서 이미 처리가 됐을 것이다!

 

따라서 P 의 개수 a 는 ⌈ D / P ⌉ 와 Q - 1 중 더 작은 값, 즉 min( ⌈ D / P ⌉ , Q - 1) 까지만 가면 된다.

그러면, 시간 복잡도는 어떻게 될까?

P ≥ Q 라면, sqrt(D) 라는 것을 알 수 있다. (증명은 "더보기" 를 클릭!)

Q ≤ P ≤ sqrt(D) 라면, min( ⌈ D / P ⌉ , Q - 1 ) = Q - 1 ≤ sqrt(D) 이다.

sqrt(D) ≤ P 라면, min( ⌈ D / P ⌉ , Q - 1 )  는 ⌈ D / P ⌉ 보단 작거나 같은데, ⌈ D / P ⌉ ≤ sqrt(D) 이다. 

 

따라서 처음에 입력 받은 두 수를 강제로 P ≥ Q 가 되게 만들어주고 코드를 이어가자.

sqrt(10억) 은 4만 이하이므로, 빠른 시간 안에 답이 계산된다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int D, P, Q;
    long long ans = 1e18;
    scanf("%d%d%d", &D, &P, &Q);
    if(P < Q) swap(P, Q); // 강제로 P >= Q 확보
    int P_cnt = min((D+P-1)/P, Q-1);

    // P*a + Q*b >= D
    for(int a = 0; a <= P_cnt; a++){
        int b = (D - P*a + Q - 1) / Q;
        ans = min(ans, (long long)P*a + (long long)Q*b);
    }
    printf("%lld", ans);
}