BOJ 1850 최대공약수 [Java]

BOJ 1850 최대공약수

- 문제 링크

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

- 문제 해설

처음에는 굉장히 막막하였다. 문제 예제들의 최대공약수를 생각해보면서 접근 방법이 떠올랐다.
문제 예제들에 유클리드 호제법을 이용해보면 된다.
111과 1111의 경우 1111=111x10 + 1, 111=111x1 + 0 이다. 그러므로 최대공약수는 1이다.
111과 111111의 경우 111111=111x1001 + 0 이다. 그러므로 최대공약수는 111이다.
1로 이루어진 수들끼리의 최대공약수는 모두 1로 이루어져있다는 사실을 추론할 수 있다.
입력 받는 데이터 A, B는 두 자연수 M, N을 이루는 1의 갯수이고, 그러므로 두 자연수 A, B의 최대공약수를 구하면 그것이 M, N의 최대공약수를 이루는 1의 갯수가 된다.

- 코드 보기

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

public class Main
{
    static long a, b;

    public static long gcd(long x, long y)
    {
        if (y == 0)
            return x;
        else
            return gcd(y, x % y);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Long.parseLong(st.nextToken());
        b = Long.parseLong(st.nextToken());

        for (int i = 0; i < gcd(a, b); i++)
            bw.write(Integer.toString(1));

        br.close();
        bw.flush();
        bw.close();
    }
}