[백준] 3955번 - 캔디 분배 (Platinum 5)

문제 링크

백준 3955번 - 캔디 분배 (Platinum 5)

문제 설명

1,000,000,000을 넘지 않는 두 자연수 K와 C가 주어져 있다.
$K \times X + 1 = C \times Y$가 되는 1,000,000,000 이하의 자연수 Y를 출력하시오.
가능한 Y가 여러개라면, 아무거나 출력해도 된다.
불가능하다면, “IMPOSSIBLE”을 출력한다.

정답 코드 및 설명

확장 유클리드 호제법을 사용하면 $K \times X + C \times Y = \textrm{gcd}(K, C)$인 정수 X, Y를 구할 수 있다.
만일 gcd(K, C) > 1이라면, 가능한 Y가 없는 것이다.
위에서 찾은 Y가 음수거나 1,000,000,000을 넘는다면, K의 정수배를 더해줌으로써 해당 범위 안에 들어오게 할 수 있다. $K \times (X - nC) + C \times (Y + nK) = K \times X + C \times Y$이기 때문이다.

이제, 확장 유클리드 호제법이 무엇인지 알아보고 이를 구현하면 된다.
유클리드 호제법은 $a < b$일 때 $\textrm{gcd}(a, b) = \textrm{gcd}(b \% a, a)$임을 이용해 재귀적으로 최대공약수를 구하는 알고리즘이다.
이를 행렬로 표현하면, $\begin{pmatrix} 0 & 1 \\ 1 & -b/a \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} b \% a \\ a \end{pmatrix}$가 된다.

이제 $b \%a < a$이므로 같은 과정을 반복할 수 있고, 최종적으로는 $\begin{pmatrix} 0 & 1 \\ 1 & -b/a \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -b_{n}/a_{n} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} 0 \\ \textrm{gcd}(a, b) \end{pmatrix}$ 가 된다.

이를 정리했을 때 $\begin{pmatrix} s & t \\ x & y \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} 0 \\ \textrm{gcd}(a, b) \end{pmatrix}$가 된다면, $ax + by = \textrm{gcd}(a, b)$임을 알 수 있다.

이 과정을 확장 유클리드 호제법이라고 한다. 이 문제에 적용할 때는 K, C의 대소 관계를 알 수 없으므로, 맨 처음에 K와 C의 대소 관계에 따라 둘을 맞바꿔주는 행렬 SWAP을 곱할지 말지를 선택했다.(코드의 19 ~ 21행 참조) 또한, 마지막에 Y를 1 이상 1,000,000,000 이하의 범위 안에 들어오게 하기 위한 과정을 수행해야 하는데 이는 코드의 24 ~ 27행에 해당한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ3955 {
    final int MAX = 1_000_000_000;
    final long[][] IDENTITY = {{1, 0}, {0, 1}};
    final long[][] SWAP = {{0, 1}, {1, 0}};
    final String IMPOSSIBLE = "IMPOSSIBLE";

    long[][] gcdMatrix = new long[2][2];
    long[][] curr = new long[2][1];

    String ans(int k, int c) {
        if (c == 1 && k == MAX) return IMPOSSIBLE;
        else if (c == 1) return String.valueOf(k + 1);
        curr[0][0] = k;
        curr[1][0] = c;
        if (k > c) gcdMatrix = IDENTITY.clone();
        else gcdMatrix = SWAP.clone();
        curr = matMul(gcdMatrix, curr);
        long gcd = gcd();
        if (gcd > 1) return IMPOSSIBLE;
        while (gcdMatrix[0][1] <= 0)
            gcdMatrix[0][1] += k;
        while (gcdMatrix[0][1] > MAX)
            gcdMatrix[0][1] -= k;
        return String.valueOf(gcdMatrix[0][1]);
    }

    long gcd() {
        if (curr[1][0] == 0) return curr[0][0];
        long[][] mat = {{0, 1}, {1, -curr[0][0] / curr[1][0]}};
        gcdMatrix = matMul(mat, gcdMatrix);
        curr = matMul(mat, curr);
        return gcd();
    }

    long[][] matMul(long[][] mat1, long[][] mat2) {
        if (mat1[0].length != mat2.length) return null;
        long[][] matMul = new long[mat1.length][mat2[0].length];
        for (int i = 0; i < mat1.length; i++) {
            for (int j = 0; j < mat2[0].length; j++) {
                for (int k = 0; k < mat2.length; k++)
                    matMul[i][j] += mat1[i][k] * mat2[k][j];
            }
        }
        return matMul;
    }

    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            String[] str = br.readLine().split(" ");
            int k = Integer.parseInt(str[0]);
            int c = Integer.parseInt(str[1]);
            System.out.println(ans(k, c));
        }
    }

    public static void main(String[] args) throws IOException {
        new BOJ3955().solution();
    }
}