#1214 쿨한 물건 구매(정수론)

이번 문제는 정수론을 잘 이해하셔야 풀기 편한 문제입니다.

 

보통 확장 유클리드 소거법이라는 것을 이용하게 되는데요.  확장 유클리드 소거법은 두개의 수가 주어졌을 때, 유클리드 소거법을 이용해서 최대공약수를 구하는 과정을 거꾸로 하는 것입니다.  예를 들어서 12와 20의 최대공약수를 구하는 과정을 볼께요.

 

\[ 8 = 20 - 12 \]

\[ 4 = 12 - 8 \]

로 12와 20의 최대공약수는 4임을 알 수 있습니다.  그리고 이 식을 거꾸로 가게 되면,

\[ 4 = 2 \times 12 - 20 \]

을 얻을 수 있죠.

 

이렇게 최대공약수를 구하는 파라미터터 (2, -1)을 얻는 것이 확장 유클리드 소거법의 목적입니다.

 

아래의 소스는 확장 유클리드 소거법을 프로그램한 것입니다.

void xgcd(long long a, long long b, long long *rg, long long *rs, long long *rt)
{
    long long r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
    long long r, s, t, q;
    while(r2)
    {
        q = r1 / r2;
        r = r1 % r2;
        r1 = r2, r2 = r;

        s = s1 - q * s2;
        s1 = s2, s2 = s;

        t = t1 - q * t2;
        t1 = t2, t2 = t;
    }
    *rs = s1, *rt = t1;
    *rg = r1;
}

 

문제를 살펴보도록 할께요.

 

https://www.acmicpc.net/problem/1214

1214번: 쿨한 물건 구매

문제를 요약해보면 d원 금액의 물건을 p원과 q원 화폐로 지불해서 사야하는데, 만들어진 금액이 d원 이상이면서 최소값을 찾는 것입니다.

 

이를 해결하기 위해서는 확장 유클리드 소거법을 이용해서 g, s, t 를 구합니다.

 

\[ g = s \times p + t \times q \]

 

이것을 이용해서 최소공배수도 구합니다.

\[ lcm = \frac{p \cdot q}{g} \]

 

d 금액을 지불할 때 최대공약수 g가 얼마나 들어가는지 구합니다.  33원을 최대공약수 10원으로 구매한다면 p원과 q원으로 구매할 수 있는 최소값은 40원 형태가 됩니다.  사실 여기까지는 최소값을 구하는 기준이고요.  이 금액이 최소공배수보다 크면, 얼마든지 최대공약수의 배수를 만들 수 있으므로, 그 금액이 최소값이 됩니다.  하지만 최소공배수보다 작다면, s와 t를 이용해서 계산을 해주어야 합니다.  지불할 수 있는 금액은 최대공약수의 배수이므로 40원을 만들 수 있다면, 그 금액으로, 아니면 50원, 60원, ... 형태로 시도하게 됩니다.  이 과정을 통해서 우리는 원하는 최소 금액을 계산할 수 있습니다.