[JAVA] 1850 유클리드 호제법

 

 

 

문제

모든 자리가 1로된 두 수의 1의 갯수가 주어졌을 때 최소공약수를 구하여라.

풀이

주어진 두 수의 1의 갯수의 최소 공약수가 바로 모든 자리가 1로된 두 수의 최소 공약수의 1의 갯수였다.!

따라서 유클리드 호제법을 사용하여 문제를 풀어주었다.

최소 공약수, gcd()

    private static long gcd(long a, long b){
        if(a % b == 0L)
            return b;
        else{
            return gcd(b, a%b);
        }
    }

유클리드 호제법을 재귀함수로 구현하여 사용했다.

        StringBuilder sb = new StringBuilder();
        long N = gcd(a, b);
        for(int i=0; i<N; i++){
            sb.append(1);
        }
        System.out.println(sb);

출력이 많이 나올 것 같아 StringBuilder로 출력할 문자열을 만들어서 출력해주었다.

전체 코드

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

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

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        StringBuilder sb = new StringBuilder();
        long N = gcd(a, b);
        for(int i=0; i<N; i++){
            sb.append(1);
        }
        System.out.println(sb);

    }

    private static long gcd(long a, long b){
        if(a % b == 0L)
            return b;
        else{
            return gcd(b, a%b);
        }
    }

}

결과