백준 1850 최대공약수

문제

풀이

public class Q1850_최대공약수 {

    static long result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        gcd(min, max);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (long i = 0; i < result; i++) {
            bw.write("1");
        }
        bw.flush();
        br.close();
        bw.close();
    }

    public static void gcd(long min, long max) {
        if (min == 0) {
            result = max;
            return;
        }
        long nam = max % min;
        gcd(nam, min);
    }

리뷰

풀이 자체는 되게 쉬운 문제였는데, 규칙을 찾아내는게 문제였다.

a(3)와 b(4)를 1로 표현하면 111, 1111이 되고
두 수의 최대공약수는 1이므로 결과도 1이 된다.
a(3)와 b(6)를 1로 표현하면 111, 111111이 되고
두 수의 최대공약수는 3이므로 결과도 111이 된다.

즉 두 수의 최대공약수만큼 1을 출력하면 되는 문제였다.

풀이는 유클리드 호제법을 이용해 두 수의 최대 공약수를 구하는데,
유클리드 호제법은
1. 최대값과 최소값을 나눈 나머지를 구하고,
2. 다시 1번의 최소값과 나머지값을 나눠 다시 두 수의 나머지 값을 구한다.
3. 이 과정을 반복해 나머지 값이 0이 되면,
나머지가 0이 되게 하는 두 수 중 최소값이 최대공약수가 된다.

이제 이렇게 구한 최대공약수를 출력하면 되는데, print문을 사용해 매 반복마다 출력을 하면 시간초과가 뜰 수 있기 때문에 BufferedWriter를 이용해 한번에 출력해주도록 하자!