[알고리즘/자바] 백준 1850번 - 최대공약수

 

 

1850번: 최대공약수

 

최대공약수를 구하는 문제인데 입력값이 조금 특이하다. 2라고 입력되었으면 11을 의미하고 3이라고 입력되었으면 111을 의미한다. 즉 2 3 이 입력되면 11과 111의 최대공약수를 구해야하는 문제다.

 

 

먼저 최대공약수(영어약자는 gcd)를 구하는 공식을 보자. 아래에 gcd(8,24)를 구하는 과정을 써봤다.

 

 

 

 

앞서 말했듯이 입력을 2와 3으로 했다면 11과 111의 최대공약수를 구해야한다.

하지만 문제에서 주어진  입력가능한 자연수의 크기는 2^63-1이다. 이를 gcd를 구하기 위해 변형하면 1의 갯수가 9223372036854775807가 된다... 당연히 이렇게 풀면 런타임 에러가 발생한다. 

 

 

문제에서 입력으로 사용되는 숫자의 최대공약수를 구해보면 규칙이 보인다.

2 3의 gcd는 1이다. 

11과 111의 gcd는 1이다.

 

3과 6의 gcd는 3이다. 

111과 111111의 gcd는 111이다.

 

즉, 문제에서 입력한 두 숫자의 gcd를 구하고, 그 결과 만큼 1을 찍어주면된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException{
		
		// 입출력
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		String t1 = bf.readLine();
		String[] numbers = t1.split(" ");
		
		// 2^63 - 1 = 9223372036854775807
		long n1 = Long.parseLong(numbers[0]);
		long n2 = Long.parseLong(numbers[1]);
		
		long repeat = gcd(n1,n2);
		
		String gcd = "1".repeat((int)repeat);

		bw.write(gcd +"\n");
		bw.flush();
		bw.close();
	}
	
	public static long gcd(long a,long b) {
		
		if(b == 0 ) return a;
		else {
			long r = a%b;
			return gcd(b,r);
		}
		
	}

		
}