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

문제

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

---

풀이(20분)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        long digits = gcd(a,b);

        StringBuilder sb = new StringBuilder();

        for(long i = 0; i < digits; i++){
            sb.append("1");
        }

        System.out.println(sb);

    }

    public static long gcd(long x, long y){
        if(y == 0){
            return x;
        }
        return(gcd(y, x%y));
    }

}

 

풀이를 보기 전에 gcd가 익숙하지 않다면 https://to-travel-coding.tistory.com/82 를 참고하여 보고 오자.

 

문제 풀이 초반 큰 수를 대해야 한다는 것을 보고 BigInteger을 사용할까 하였다. 하지만 이렇게 하더라도 시간이 매우 오래 걸리는 문제가 발생할 수 있고, 규칙을 찾고자 했다.

 

1과 11은 공약수를 1로 가진다.

111은 11과 공약수가 없다.

1111은 11에 101을 곱한 것과 같다.

111111은 111에 1001을 곱한 것과 같다. 

 

이런 식으로 규칙을 찾다 보면 2 4 8 16으로 자릿수가 증가하는 배수 라인이 있고,

3 6 12로 증가하는 배수 라인이 있다.

(여기서 배수 라인이란 11 -> 1111 -> 11,111,111을 말한다.)

 

즉, 자릿수끼리의 공약수를 찾으면 된다는 소리이기도 하다.

자릿수 4(1111) 과 자릿수 8(11,111,111)의 최대 공약수를 찾아라! 하면 4와 8의 공약수인 4가 1의 개수(1111)가 된다는 소리이다!

최종적으로 코드로 구현해주면 된다.

(StringBuilder을 사용하지 않으면 시간 초과가 발생한다.)