BOJ 3955

문제 설명

• 문제: 백준 3955

이 문제는 주어진 자연수 K, C에 대해서 $KX_K + 1 = CX_C$가 되는 자연수 $X_K, X_C$를 찾는 문제, 더 정확히는 $X_C$를 찾는 문제입니다. $K, X_K, C, X_C$는 각각 사람의 수, 각 사람이 받는 사탕 수, 사탕의 수, 사탕 봉지의 수를 나타냅니다. 위 방정식의 해를 구하기 위해 베주 항등식과 확장 유클리드 호제법을 이용합니다.

사전 지식

베주 항등식

베주 항등식을 설명하기 전에, 주어진 식을 다음과 같이 아주 조금만 변경해 봅시다.

$$ CX_C + K(-X_K) = 1 $$

크게 달라진 점은 없지만 Cx + Ky = 1의 해를 구하는 문제라는 점을 알 수 있습니다. 이제 베주 항등식을 보죠.

• a, b가 정수이고, 최대공약수가 d일 때, ax + by = d를 만족하는 정수 x, y가 존재한다.
• ax + by로 표현되는 모든 정수는 d의 배수이다.

이 포스트는 수학적인 원리까지 깊게 들어가지는 않기 때문에 별도의 증명을 하지는 않겠습니다. 다만 여기서 알 수 있는 정보가 꽤 있죠. 만약 a, b의 최대공약수가 1이 아니라면, 즉 서로소가 아니라면, ax + by = 1을 만족하는 정수 x, y가 존재할 수 있을까요? 두 번째 문장 때문에 불가능하단 걸 알 수 있습니다. 즉, 입력으로 주어지는 C랑 K가 서로소여야만 해를 구할 수 있고, 또 첫 번째 문장 때문에 항상 존재함을 알 수 있습니다.

(베주 항등식까지 갈 필요도 없이, 이 문제만 보고도 C와 K가 서로소가 아니라면 문제를 해결할 수 없다는 것을 아실 수 있을 겁니다. 잘 생각해보세요!)

확장 유클리드 호제법을 이용한 풀이

존재성을 밝혔으니 어떻게 구할지 찾아 봅시다. 이를 위해서는 확장 유클리드 호제법을 이용합니다. 유클리드 호제법이 최대공약수를 구하는 것에 초점을 맞췄다면, 확장 유클리드 호제법은 베주 항등식에 등장하는 x, y를 구하는 데에 중점을 둡니다.

유클리드 호제법을 통해 두 수의 최대 공약수를 구하는 과정을 되살펴봅시다. 다음과 같은 절차로 진행이 됩니다.

$$ a = r_0, , b = r_1 \ r_0 = r_1 * q_1 + r_2 \ r_1 = r_2 * q_2 + r_3 \ … \ r_{k-1} = r_k * q_k + r_{k+1} $$

이 과정을 $r_{k+1}$이 0이 될 때까지 반복하게 되면, $r_{k}$가 a와 b의 최대공약수임을 나타내는 것이 유클리드 호제법입니다. 이 과정에서 나온 $r_{i}, q_{i}$들을 이용해 봅시다.

우선 $r_{i}, (i <= k)$ 들은 모두 $r_{k}$의 배수임을 알 수 있고, 베주 항등식에 의해 $r_{k} = ax + by$ 형태로 표현이 됩니다. 베주 항등식에 의해 임의의 k 이하의 i에 대해 $r_{i} = ax_i + by_i$ 형태로 표현이 된다는 사실 역시 알 수 있죠.

이제 이 $x_i$와 $y_i$를 구하면 됩니다. $r_0 = a$이므로 $x_0 = 1, y_0 = 0$이고 $r_1 = b$ 이므로 $x_1 = 0, y_1 = 1$으로 둘 수 있습니다. 이제 수학적 귀납법을 이용해 다음을 증명해봅시다.

$$ x_{i+1} = x_{i-1} - q_i * x_i \ y_{i+1} = y_{i-1} - q_i * y_i $$

i = 1인 경우

$$ \begin{aligned} r_2 &= r_0 - r_1*q_1 \ &= a - q_1b \ &= (1 - 0 * q_1)a + (0 - 1 * q_1)b \ &= (x_0 - q_1 * x_1)a + (y_0 - q_1 * y_1)b \end{aligned} $$

입니다. 따라서 만족합니다.

마찬가지로 $i <= k-1$일 때 모두 만족한다는 가정하에,

$$ \begin{aligned} r_{k+1} &= r_{k-1} - r_kq_k \ &= r_{k-1} - r_kq_k \ &= (x_{k-1} - q_k * x_k)a + (y_{k-1} - q_k * y_k)b \end{aligned} $$

이므로 $i = k$일 때 역시 만족합니다.

증명에 대한 부분은 자세히 몰라도 됩니다. 중요한 점은, $x_i$ 와 $y_i$를 유클리드 호제법을 이용해 구해 놓은 $q_i$를 이용해서 구할 수 있다는 점이죠. a와 b가 서로소라면 종국에는 $1 = r_n = ax_n + by_n$ 형태로 표현될 것이므로, $x_n$과 $y_n$을 구하면 됩니다.

접근 방법

이 문제는 문제에 숨겨진 함정이 조금 있습니다. 원래 문제로 돌아와 $CX_C + K(-X_K) = 1$에서 $X_C$를 구한다고 생각해 봅시다.

서로소

$K, C$가 서로소여야 함을 먼저 확인해야 합니다. 만약 둘의 최대공약수가 1 초과라면 $Kx + Cy = 1$을 만족하는 정수 x, y가 존재하지 않기 때문에 문제의 해답이 없습니다.

$X_C$가 음수

확장 유클리드 호제법을 통해 구한 $X_C$가 음수일 수 있습니다. 이 경우에는 양수인 해를 찾아서 바꿔줘야 합니다.

주어진 식의 좌변에 KC를 더하고 빼 주면 다음과 같이 변경됩니다.

$CX_C + K(-X_K) = (CX_C + KC)+ (K(-X_K) - KC)= C(X_C + K) + K(- X_K - C)$

즉, $X_C+K$ 역시 해가 된다는 것을 의미합니다. 여기서 $K$는 자연수이므로 무조건 $X_C$보다 크다는 것을 알 수 있습니다. 따라서 $X_C$가 양수가 될 때까지 $K$를 더해주면 됩니다.

$X_K$가 음수

$X_K$가 음수인 경우 역시 만족하지 않습니다. $X_K$는 각 사람이 몇 개의 사탕을 받는지를 나타내는 수고, 항상 양수여야 합니다. 반대로 얘기하면 $-X_K$가 양수인 경우 음수로 만들어줘야 합니다. $-X_K$에서 $C$를 빼면서 음수로 만들어주면 됩니다.

$X_C$가 $10^9$ 이상

당연하지만 이 경우 역시 확인해줘야 합니다. $K, C$가 최대 $10^9$까지 될 수 있으므로 일어날 수 있는 일입니다.

코드 설명

유클리드 호제법

입력으로 K, C를 받아 유클리드 호제법을 통해 얻은 몫을 구합니다. quotients라는 벡터에 몫들을 저장합니다.

또한 최대공약수가 1이 아닌 경우에는 -1을 반환해 문제의 해가 없다는 점을 알려줍니다.

int get_candy(int K, int C){
    long long r0 = K;
    long long r1 = C;
    long long r2 = K % C;

    std::vector<int> quotients;

    while(r2 != 0){
        quotients.push_back(r0 / r1);
        r0 = r1;
        r1 = r2;
        r2 = r0 % r1;
    }

    if(r1 != 1)
        return -1;

확장 유클리드 호제법

확장 유클리드 호제법을 위해 2.2에서 설명한 $x_i$와 $y_i$를 구합니다. 각각 K의 계수, C의 계수를 나타내는 coeff_K, coeff_C 벡터에 저장합니다. 2.2에서 계수들을 구하는 식을 이용해 계산합니다.

    std::vector<int> coeff_K;
    coeff_K.push_back(1);
    coeff_K.push_back(0);

    std::vector<int> coeff_C;
    coeff_C.push_back(0);
    coeff_C.push_back(1);

    int next_coeff_K, next_coeff_C;

    for(int q:quotients){
        next_coeff_K = coeff_K[coeff_K.size() - 2]
                       - q * coeff_K[coeff_K.size() - 1];

        next_coeff_C = coeff_C[coeff_C.size() - 2]
                       - q * coeff_C[coeff_C.size() - 1];


        coeff_K.push_back(next_coeff_K);
        coeff_C.push_back(next_coeff_C);

    }

$X_C$ 조정

마지막으로 $X_C$를 조정해줍니다.

$X_C$가 음수인 경우에는 $K$를 더해주고, $-X_K$가 양수인 경우에는 $C$를 뺍니다. 이후 $X_C$가 상한을 넘은 경우 역시 -1을 반환해가 없다는 사실을 알려주고, 그렇지 않은 경우 $X_C$를 반환합니다.

long long X_C = (long long)coeff_C.back();
long long neg_X_K = (long long)coeff_K.back();

while((X_C <= 0) || (neg_X_K >= 0)){
    X_C += K;
    neg_X_K -= C;
}

if(X_C > 1000000000)
    return -1;

else
    return (int)X_C;

여담

정수론을 이용해 푸는 문제였습니다. 수학적인 아이디어를 생각하는 것은 쉬웠으나 여러 예외를 고려해야 하는 문제였습니다.

코드 원본은 여기를 참고해 주시면 됩니다.

References

1. Bézout’s identity
2. Extended Euclidean algorithm
3. 백준 3955