[JAVA] 백준 (실버1) 1850번 최대공약수

링크

https://www.acmicpc.net/problem/1850

---

문제 설명

정답률 35.389%
모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

---

입력 예제

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

3 4

---

출력 예제

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

1

---

풀이

주어진 입력값들에 대해 최대 공약수를 구하는 문제이다. 입력값은 길이를 의미하는데 예제의 경우 두 자연수 A, B는 111과 1111이 된다. 이렇게 수를 변환한 뒤 최대 공약수를 구하면 되지만 길이의 최댓값이 $2^{63}$이므로 메모리 초과가 발생한다.

예제들을 보면 A와 B의 최대 공약수는 입력값들의 최대공약수 길이를 나타낸다. - 3, 4의 최대 공약수는 1이고 A와 B의 최대 공약수는 1

• 3, 6의 최대 공약수는 3이고 A와 B의 최대 공약수는 111
• 500...000, 500...002의 최대 공약수는 2이고 A와 B의 최대 공약수는 11

입력값의 최대 공약수를 구한 뒤 그 길이만큼 1를 출력해주면 된다.

StringBuilder sb = new StringBuilder();
long gcm = GCM(a, b);
for (int i = 0; i < gcm; i++) {
    sb.append(1);
}

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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());

        StringBuilder sb = new StringBuilder();
        long gcm = GCM(a, b);
        for (int i = 0; i < gcm; i++) {
            sb.append(1);
        }

        System.out.println(sb);
    }

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