[백준 알고리즘] Q1850 최대공약수

1. Java 구현

import java.util.*;

public class Main {

	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    long a = sc.nextLong();
	    long b = sc.nextLong();
	    
	    System.out.println(getResult(getGCD(a, b)));
	    sc.close();

	}
	
	public static long getGCD(long a, long b) {
		long max = Math.max(a, b);
		long min = Math.min(a, b);
		
		if (max % min == 0) return min;
		else return getGCD(max % min, min);
	}
	
	public static String getResult(long n) {
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++)
			sb.append("1");
		
		return sb.toString();
	}	

}

2. 코드 설명

문제는 복잡하지만, 단순하게 생각하면 최대공약수를 구하는 문제이다. 문제 조건을 보면 1의 갯수가 2^63까지 될 수 있기 때문에 굉장히 큰 수가 만들어진다.

 BigInteger를 사용해야 하나..? 그럼 시간내 답을 구할수 없을텐데..? 라는 생각이 들었다.

 그런데 2^63이 마치... BigInteger가 아닌 long을 이용해야 하지 않을까? 라는 생각이 들었다.

 예제로 보게 되면, 6은 111111 이고 4는 1111 이다. 그리고 6과 4의 최대공약수는 2이고, 여기서는 11이라 할 수 있다.

 최대공약수는 두 수의 공통적인 약수 중 가장 큰 값을 의미한다. 이 전제를 기억하고 6과 4를 다시 표현해보겠다.

 6 --> 11 * 10000 + 11 * 100 + 11 이고, 4는 11 * 100 + 11 이다. 그리고 이 두 수의 공통적인 부분은 11 즉 2이다.