Topcoder SRM 537 Div1(Easy) KingXNewCurrency

https://community.topcoder.com/stat?c=problem_statement&pm=11817

A, B, X <= 200

입력 A, B, X 가 주어진다.

서로 다른 화폐가 두개 A, B가 있다. A와 B를 적절히 섞어서 지불할 수 있는 모든 금액을

X, Y 로도 지불할 수 있도록 하는 X와 다른 Y의 개수를 구하는 문제이다.

이 문제를 세가지 방법으로 풀어보았다.

(N <= 200)

풀이1 : O(N^3) 방법(브루트 포스)

풀이2 : O(N^2) 방법(dp)

풀이3 : O(NlgN) 방법(확장유클리드)

우선 조금 생각을 해보면 A, B를 X, Y로 커버하려면 X, Y 를 적절히 섞어서 A와 B를 모두 만들 수 있어야 함을

알 수가 있다. 너무 당연하지만 증명을 해보자면, 만약 X, Y 를 섞어서 A를 만들 수 없다고 하자, 그러면

A, B 로는 금액 A를 지불할 수 있지만(A 1개, B 0개로) X, Y로는 지불 하지 못하므로 자명하다.

그러면 만약 X, Y로 A, B 를 둘다 만들 수 있다면 A, B를 섞어서 만들 수 있는 금액들도 모두 만들 수 있는것이

너무나도 당연하다. 그러므로 X, Y 를 상수 a, b 로 보면

ax + by = A, ax + by = B 

이 두 디오판토스 방정식이 둘다 음이 아닌 정수 쌍 해가 존재해야 한다면 그 X, Y는 가능한 것이다.

그렇다면 Y 후보는 몇개가 있을까? 우선 X가 A와 B 모두를 나눌 수 있다면 Y는 사용할 필요도 없이

무조건 A와 B를 만들 수가 있으므로 예외 처리를 해준다면, 그 외의 우리가 고려해줘야하는 경우는

A와 B 둘 중 하나를 만들 때에는 무조건 Y를 1개이상 사용해야 한다는 것이다. 그런데

Y가 max(A, B) 보다 크다면 Y를 한개라도 사용하면 절대로 A와 B를 모두 만들 수 없게 된다.

그렇기 때문에 Y는 무조건 max(A, B) 이하이다. 그럼 Y는 최대 200 이라는 것을 알 수가 있다.

그럼 200개의 Y에 대해 반복문을 돌리는데 A와 B가 200이하이기 때문에 X와 Y를 사용하는 개수도

아무리 많아봐야 200개를 넘을 수가 없다는 것을 알 수 있으므로 모든 Y에 대해 X와 Y의 개수를 돌려서

두 방정식을 모두 만족하는 X, Y 쌍이라면 답을 세는 식으로 하면 O(N^3) (N <= 200) 에 답을 구할 수가있다.

이것이 브루트 포스 풀이이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
class KingXNewCurrency {
    public:
    int howMany(int A, int B, int X) {
        int ans = 0;
        if(A % X == 0 && B % X == 0) return -1;
        for(int Y = 1; Y <= max(A, B); Y++){
            int ok1 = 0, ok2 = 0;
            for(int i = 0 ; i * X <= A; i++){
                for(int j = 0 ; i * X + j * Y <= A; j++){
                    if(i * X + j * Y == A) ok1 = 1;
                }
            }
            for(int i = 0 ; i * X <= B; i++){
                for(int j = 0 ; i * X + j * Y <= B; j++){
                    if(i * X + j * Y == B) ok2 = 1;
                }
            }
            if(ok1 && ok2) ans++;
        }
        return ans;
    }
};

그런데 모든 Y에 대해 가능한 X, Y 개수를 O(N^2) 에 모두 돌리지 않아도 

dp[i] = 'ax + by = i ' 꼴의 음이 아닌 정수 쌍 (x, y) 의 존재 여부

라고 하면 dp[i] 가 1이라면 이 때의 해를 (x', y') 라고 할 때 양변에 a나 b를 더하면

dp[i + a] 도 해 (x' + 1, y') 가 있으므로 1이고, dp[i + b] 도 해(x', y' + 1) 가 있으므로 1

이라는 것을 알 수가 있으므로 점화식이 나온다.

이렇게 하면 각각의 X,Y 쌍에 대해 O(N) 에 계산이 가능하므로 전체 시간복잡도가 O(N^2)이 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int exist[203];
class KingXNewCurrency {
    public:
    int howMany(int A, int B, int X) {
        int ans = 0;
        if(A % X == 0 && B % X == 0) return -1;
        for(int Y = 1; Y <= 200; Y++){
            memset(exist,0,sizeof(exist));
            exist[0] = 1;
            for(int i = 0; i <= 200; i++){
                if(!exist[i]) continue;
                if(i + X <= 200) exist[i + X] = 1;
                if(i + Y <= 200) exist[i + Y] = 1;
            }
            if(exist[A] && exist[B]) ans++;
        }
        return ans;
    }
};
 

마지막으로 확장 유클리드 풀이는 굳이 설명하지 않겠다. 그냥 디오판토스 방정식이 나오면

특정 구간의 해의 개수를 확장 유클리드로 O(NlgN) 으로 풀 수 있는 것이 알려져있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll xGCD(ll a, ll b, ll& x, ll& y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll ret = xGCD(b, a % b, x1, y1);
    x = y1, y = x1 - (a / b) * y1;
    return ret;
}
 
ll gcd(ll a, ll b){
    ll trash;
    return xGCD(a, b, trash, trash);
}
 
ll findRng(ll x0, ll y0, ll a, ll b){
    if(y0 <= 0) {
        swap(x0, y0);
        swap(a, b);
    }
    ll g = gcd(a, b);
    ll dx = b / g, dy = - a / g;
    ll t1, t2;
    if(x0 < 0) t1 = (-x0 + dx - 1) / dx;
    else t1 = 0;
    t2 = y0 / (-dy);
    return max(0ll, t2 - t1 + 1);
}
 
class KingXNewCurrency {
    public:
    int howMany(int A, int B, int X) {
        int ans = 0;
        if(A % X == 0 && B % X == 0) return -1;
        for(int i = 1; i <= max(A, B); i++){
            ll a, b, g, rng1, rng2;
            g = gcd(X, gcd(i, A));
            if(gcd(X / g, i / g) != 1) continue;
            xGCD(X / g, i / g, a, b);
            rng1 = findRng(a * A / g, b * A / g, X / g, i / g);
            g = gcd(X, gcd(i, B));
            if(gcd(X / g, i / g) != 1) continue;
            xGCD(X / g, i / g, a, b);
            rng2 = findRng(a * B / g, b * B / g, X / g, i / g);
            if(A % X == 0 || A % i == 0) rng1 = 1;
            if(B % X == 0 || B % i == 0) rng2 = 1;
            if(rng1 && rng2) ans++;
        }
        return ans;
    }
};