[백준/Java] #2824 최대공약수

 

 

문제

 

 

 

 

 

코드

 

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        BigInteger a = getValue();
        BigInteger b = getValue();

        bw.write(gcd(a, b));
        bw.close();
    }

    static BigInteger getValue() throws IOException {
        int N = Integer.valueOf(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        BigInteger val = new BigInteger("1");

        for (int i = 0; i < N; i++) {
            val = val.multiply(new BigInteger(st.nextToken()));
        }
        return val;
    }

    static String gcd(BigInteger a, BigInteger b) {
        while (b.compareTo(BigInteger.ZERO) > 0) {
            BigInteger temp = a;
            a = b;
            b = temp.remainder(b);
        }
        String result = a.toString();
        if (result.length() > 9) return result.substring(result.length() - 9);
        return result;
    }
}

 

숫자가 매우 크기 때문에 BigInteger를 사용했고, 숫자 A와 B를 구하는 메서드와 최대공약수를 구하는 메서드를 만들었다.

 

저번에 비슷한 문제에서 재귀함수를 썼을 때 메모리 초과 문제가 있었기 때문에 반복문으로 최대공약수를 구하였다.

최대공약수를 구한 뒤, 값의 길이가 9자리가 넘어가면 뒤에서부터 9자리만 구해 return.

 

getValue()에서 사용하기 위해 BufferedReader는 static 멤버변수로 선언했다.

(메서드 내에서 선언하면 NumberFormat 예외 발생)