[1850] 최대공약수 (JAVA)

# 문제 설명

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

---

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

---

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

 

# 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long gcd = GCD(A, B);

        while (gcd > 0) {
            sb.append("1");
            gcd--;
        }

        System.out.print(sb);
    }

    public static long GCD(long a, long b) {
        long big = Math.max(a, b);
        long small = Math.min(a, b);
        long result = 0;

        while (true) {
            result = big % small;

            if (result == 0) {
                return small;
            }

            big = small;
            small = result;
        }
    }
}

 

이 문제는 예제 출력을 바탕으로 규칙을 찾을 수 있다.

수의 길이를 나타내는 두 수의 최대 공약수는 실제 숫자의 최대 공약수의 길이를 나타낸다.

 

예를 들어 두 수의 길이가 3과 6일 때, 3과 6의 최대 공약수는 3이다.

실제 숫자는 111, 111111이고, 두 수의 최대 공약수는 111이다.

즉 두 수의 길이의 최대 공약수가 실제 두 수의 최대 공약수의 길이이다.

 

위 규칙을 이용하여 문제를 풀었다.

두 수의 길이 A, B의 최대 공약수를 gcd에 저장한다.

gcd의 길이만큼 1을 출력한다.

 

최대 공약수는 유클리드 호제법을 이용하여 구했다.