코딩 테스트 [정수론] - 최대 공약수 구하기

모든 자리가 1로만 이뤄진 두 자연수 A와 B가 주어져 있다. 이때 A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어 A가 111이고 B가 1111일 때 A와 B의 최대 공약수는 1이다. A가 111이고 B가 111111일 경우에는 최대 공약수가 111이다.

(시간 제한 2초)

---

입력

1번째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 $2^{63}$보다 작은 자연수다.

출력

1번째 줄에 A와 B의 최대 공약수를 출력한다. 정답은 1,000만 자리를 넘지 않는다.

예제 입력
500000000000000000 500000000000000002	// A와 B의 길이

예제 출력
11

---

1단계 - 문제 분석하기

예제 입력과 같이 입력값이 크면 단순한 방법으로 최소 공배수를 찾을 수 없다. 하지만 주어진 예제를 바탕으로 다음 규칙을 찾을 수 있다

· 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다.
· 즉 3, 6의 최대 공약수 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타난다.

2단계 - 손으로 풀어 보기

1 유클리드 호제법을 이용해 주어진 A, B의 최대 공약수를 구한다.

2 공약수의 길이만큼 1을 반복해 출력한다.

최대 공약수가 2이므로 2번 반복해 1을 출력 -> 11

3단계 - sudo코드 작성하기

a(1번째 수) b(2번째 수)

결괏값 = gcd(a, b)
while(결괏값 > 0)
{
	1출력
    결괏값--;
}

gcd(int a, int b)
{
	if(b == 0)
    	return a;
    else
    	gcd(b, a % b);
}

4단계 - 코드 구현하기

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Q43 {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long a = sc.nextLong();
        long b = sc.nextLong();

        long result = gcd(a, b);

        while (result > 0){
            bw.write("1");
            result--;
        }
        bw.flush();
        bw.close();
    }

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

---

• Do it! 알고리즘 코딩테스트 자바 편