[1850] 최대공약수

✔ 최대공약수

[백준 1850]

문제 분석하기

입력값이 크면 단순한 방법으로 최소 공배수를 찾을 수 없음

그러므로 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다는 규칙을 바탕으로 문제에 접근

예) 3, 6의 최대 공약수는 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타낼 수 있음

손으로 풀어보기

1. 유클리드 호제법을 이용해 주어진 A, B의 최대 공약수를 구함
2. 공약수의 길이만큼 1을 반복해 출력

슈도코드 작성하기

a(1번째 수)
b(2번째 수)
결괏값 = gcd(a, b)
결괏값만큼 1을 반복해 출력하기

gcd {
    if(b가 0이면) a가 최대 공약수
    else gcd(작은 수, 큰 수 % 작은 수)
}

코드 구현하기

/**
 * 1850) 최대공약수
 */
public class D043_1850 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // a(1번째 수)
        long a = sc.nextLong();
        // b(2번째 수)
        long b = sc.nextLong();
        // 결괏값 = gcd(a, b)
        long result = gcd(a, b);
        // 결괏값만큼 1을 반복해 출력하기
        while (result > 0) {
            bw.write("1");
            result--;
        }
        bw.flush();
        bw.close();
    }

    // 최대 공약수 함수 구현하기
    public static long gcd(long a, long b) {
        // if(b가 0이면)
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // gcd(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }
}