[BaekJoon] 4342 유클리드 게임 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int maxNum;
    static int minNum;

    static boolean input() {
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();

        if (num1 == 0 && num2 == 0) {
            return false;
        }

        maxNum = Math.max(num1, num2);
        minNum = Math.min(num1, num2);

        return true;
    }

    /*
     * 두 수 중 더 큰 수를 max, 더 작은 수를 min이라고 칭할 때, 3가지 케이스로 나눠볼 수 있다
     *  1) max % min == 0
     *      - 해당 상황이 발생한다면 이 상황을 맞이한 플레이어가 항상 이긴다
     *  2) max - min < min
     *      - 해당 상황이 발생한다면 누가 이길지는 확신할 수 없다
     *      - 이 상황에서 알 수 있는 것은 이러한 상황이 발생한다면 이후에도 이와 같은 상황이 반복된다는 것이다
     *      - cf)
     *          - min < max 이고 max - min < min을 만족한다
     *          - 그렇다면 한 번 유클리드 게임을 진행한 후에는 (max, min)에서 (min, max - min)으로 변한다
     *          - 그렇다면 유클리드 게임을 한 번 진행한 후 원래 2번 상황인 max - min < min이 만족되는지 확인해보자
     *          - min - (max - min) < min -> 2 * min - max < min -> min - max < 0 -> min < max
     *          - 초기 조건인 min < max를 만족한다
     *          - 그러므로 이 상황이 발생한다면 이후에소 계속 이와 같은 상황이 반복된다
     *  3) max - min > min
     *      - 해당 상황이 발생한다면 이 상황을 맞이한 플레이어가 항상 이긴다
     *      - ex. (28, 6)를 예시로 들어보자
     *              - 유클리드 게임을 한 번 진행했을 때 1번 상황은 만들 수 없으니 2번 상황이 되도록 만들어보자
     *                  - 2번 상황은 누가 이기는지 알 수 없고 계속 2번 상황이 반복되므로 두 경우 모두 끝까지 진행해본다
     *              - 1) (10, 6) -> (6, 4) -> (4, 2) -> 후공 이김
     *              - 2) (6, 4) -> (4, 2) -> 선공 이김
     *              - 결국, 선공이 이기는 경우가 반드시 존재한다!
     *                  -> 그렇다면 선공이 이 경우를 선택하여 진행한다면 선공이 반드시 이기게 된다!
     *      - 결국, 3번 상황을 맞이하면 해당 상황을 맞이한 플레이어가 이긴다!
     *
     * 이와 같은 규칙을 이용하여 게임에서의 승자를 확인한다
     */
    static void solution() {
        if (gcd(maxNum, minNum)) {
            answer.append("A wins").append('\n');
            return;
        }
        answer.append("B wins").append('\n');
    }

    static boolean gcd(int max, int min) {
        if (max % min == 0) {
            return true;
        }
        if (max - min < min) {
            return !gcd(Math.max(max - min, min), Math.min(max - min, min));
        }
        return true;
    }

    public static void main(String[] args) {
        while (true) {
            if (!input()) {
                break;
            }
            solution();
        }

        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}