[BOJ][Java] 1850번 최대공약수

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1850

 

이 문제는 최대공약수를 구해야 하는 문제이다. 

입력값 A, B 가 3, 4일 때 각각 111, 1111으로 변환된다고 생각하면

입력값이 너무 커지기 때문에 1 로 변환하지 않고 그대로 최대공약수를 구한 다음

해당 최대 공약수만큼 1을 출력해 주면 된다.

 

여기서 최대공약수를 구할 때는 유클리드 호제법을 사용하면 된다.

유클리드 호제법이란 두 숫자 a, b의 최대 공약수를 구하는 알고리즘으로

두 수중 더 큰 값 % 작은 값을 하여 나머지가 나오면

해당 나머지가 0 이면 이때의 작은 값을 최대공약수로 리턴하고

나머지가 0이 아니라면 이번에는 기존의 작은 값을 큰 값에 대입,

작은 값에는 나머지를 넣고 나머지연산을 반복하는 알고리즘이다.

 

package boj;

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

public class BOJ1850 {
    public static void main(String[] args) throws Exception {
        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());

        long count = gcd(a,b);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < count; i++){
            sb.append("1");
        }

        System.out.println(sb);

    }
    static long gcd(long a, long b){
        long max = 0;
        long min = 0;
        if(a >= b) {
            max = a;
            min = b;
        }else{
            max = b;
            min = a;
        }

        while(true){
            long temp = max % min;
            if(temp == 0) return min;
            else{
                max = min;
                min = temp;
            }
        }


    }
}