[BAEKJOON] - 1850번 : 최대 공약수

1850번 문제 링크

⏲️ 시간 복잡도

• 최소 공배수 또는 최대 공약수를 물어보는 문제는 "유클리드 호제법"을 활용하여 문제를 풀어주면 됩니다.

📜 로직

• 처음 문제를 확인한 뒤, 변수에 담길 최대 범위가 2^63보다 작은 수라는 내용을 확인하고 long 자료형을 사용해야 하는 것을 잘 확인해야 합니다.
• 그 다음으로 두 입력값 간의 최대 공약수를 자릿수로 갖는 1로 표현된 값을 출력해주면 문제는 쉽게 풀 수 있습니다.

1. 유클리드 호제법을 사용하기 위해 gcd 메서드 정의.
2. 입력값을 long 자료형으로 받은 뒤, 최대 공약수 구하기.
3. 결과값 만큼 반복문을 돌려 1의 값으로 변환.

😀 성공

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());

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

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

        long result = gcd(b, a);

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

        br.close();

        System.out.println(sb);
    }

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