[BOJ] 쿨한 물건 구매

쿨한 물건 구매

TimeLimit	MemoryLimit	Condition	TAG
0.5s	128MB	(1 ≤ D, P, Q ≤ 10^9)	Implementation, Math

음.. 접근 방법은 보자마자 생각을 해냈지만.. 이 시간을 어떻게 줄일까 생각을 하다가 열심히 방정식 가지구 으쌰으쌰 하니까 조건을 알아내서 풀었습니다.

기본적인 아이디어는 큰 수의 개수를 확정짓는 하나의 값 N을 찾는다고 한다면 N을 확정하는 순간 다른 화폐의 개수도 확정되겠죠? 이거 이용해서 구현하면 됩니다. 이때 시간 초과를 피하기 위해서 범위를 효율적으로 계산하는게 진짜 중요한데 큰 값을 기준으로 N을 늘려가면서 [d + 작은값] 보다 안 크도록 유지해주면 됩니다.

D \leq (N - P) Q + (M + Q) P

위 식에서 $N \geq P$ 인 것을 알 수 있다. 이후에 이제 $N \geq P$ 에서 최대의 $P$ 의 값을 가져오게 된다면 이후에 더 올리는 것은 무의미하다. 왜냐하면 결국 조정되면서 현재 조정하는 값 대신에 다른 값이 작아지고 결국 0부터 왔다면 다시 방문했던 값을 보기 때문에 반복된다. 그래서 우리는 $N < P$ 를 알 수 있고, $limit = p$ 가 되는 것을 알 수 있다.

<참고: https://www.acmicpc.net/board/view/96265 >

정답 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <random>
#include <cmath>
using namespace std;
using ll = long long;

ll d, p, q;
ll gcd(ll a, ll b){
    while(b != 0){
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}
ll lcm(ll a, ll b){ return a * b / gcd(a, b); }


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> d >> p >> q;
    
    if(p == 1 || q == 1) {
        cout << d;
        return 0;
    }
    
     
    ll a = max(p, q), b = min(p, q);
    
    p = a;
    q = b;
    
    if(p%q == 0){
        if((ll)(d / q) * q == d) cout << d;
        else cout << (ll)(d / q) * q + q;
        return 0;
    }
    
    // 일단 p, q가 1인 경우가 제외됨으로 1e9까지 돌 ㅑfor문이 지금 1e9 / 2가 되버림 잠시만 시간이 1e5/5임 이게 맞음? 와 잠시만
    if(q == 2){
        if(d % q == 0) cout << d;
        else{
            if(p % 2 == 0) cout << d + 1;
            else{
                if(d - q >= p) cout << d;
                else cout << d + 1;
            }
        }
        
        return 0;
    }
    ll limit = q;
    ll result = min((ll)(d / q) * q + q, (ll)(d / p) * p + p);
    
    // 100 3 6
    //
    bool check = false;
    for(ll i = 0; i < limit ; i++){
        
        ll current = p * i;
        if(current > d + q) break;

        current += (ll)(abs(d - current) / q) * q;

        current = min(current + q, abs(d - current) % p == 0? d : (ll)((abs(d - current) / p)+1) * p + current);
        
        result = min(current, result);
//        cout <<"result: " << result << " current: " << current << "\n";
        if(result == d) break;
    }
    cout << result;
    

    return 0;
}