BOJ_1850 : 최대공약수

👉 문제링크

1850번: 최대공약수

---

---

🔸 문제 분석 🔸

• A와 B의 길이만큼 1로 이루어진 수의 최대공약수를 구하는 문제이다.

🔸 문제 풀이 🔸

• 실제 수는 아주 긴 1로 이루어진 숫자들이지만, 그냥 A와 B의 최대공약수를 구하면 되는 문제이다.
  • 유클리드호제법을 사용해서 최대공약수를 구하고, 그 수만큼 반복해서 1로 이루어진 수를 만들어 출력한다.
•  

🔸 코드 🔸

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

public class Main {
    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());
        StringBuilder sb = new StringBuilder();

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long gcd = A > B ? gcd(A, B) : gcd(B, A);

        for (long i = 0; i < gcd; i++) {
            sb.append('1');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static long gcd(long A, long B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }
}

🔸 코드 해석 🔸

• A와 B의 크기가 int를 벗어나므로, long으로 선언한다.
• 유클리드호제법으로 입력된 A, B의 최대공약수를 구한다.
• 구해진 최대공약수 만큼 반복해서 '1'로 이루어진 수를 만들어 출력한다.

---

🔸 end 🔸

• 유클리드 호제법과 1로 이루어진 수를 직접 만드는 것이 아닌, 그 길이로 최대공약수를 구하면 된다는 걸 눈치채면 쉽게 풀이할 수 있는 문제였다.