[백준 1850] 최대공약수 (JAVA)

백준 1850번 문제  - 최대공약수

1850번: 최대공약수

---

문제 분석

 

 

• 두 자연수의 1의 개수를 입력 받아, 최대 공약수를 출력해라.

---

해결 키 포인트

 

• 유클리드 호제법을 이용해 최대 공약수를 구한다
  • 두 수의 1의 개수를 가지고, 최대 공약수의 1의 개수를 알아낸다
• 해당 수 만큼 1을 출력
  • 처음 시도, sum = sum * 10 + 1 로 구현하였지만 문제 존재
  • 결국엔, bw.write("1")로 구현하여 성공

---

유클리드 호제법

MOD연산을 이용해 두 수의 최대 공약수를 구하는 알고리즘이다.

 

MOD 연산 :  두 값을 나눈 나머지를 구하는 연산
ex. 10 MOD 4 = 2 (10 % 4 = 2)

 

유클리드 호제법 알고리즘

 

1. 큰 수를 작은 수로 나누는 MOD 연산 수행

2. 앞 단계에서의 작은 수와 MOD 연산 결과 값(나머지)으로 MOD 연산 수행

3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

 

Do It! 알고리즘 코딩 테스트 기본

---

코드

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

        // 두 수의 1의 개수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        // 최소 공약수의 1의 개수 구하기
        long sum = (A >= B) ? A % B : B % A;
        long gcd = Math.min(A, B);

        while (sum > 0) {
            long temp = sum;
            sum = gcd % sum;
            gcd = temp;
        }

        // 실제 최대 공약수 제작
        for(int i=0;i<gcd;i++) {
            bw.write("1");
        }
        bw.flush();
        bw.close();

    }
}