[BaekJoon] 1850 최대공약수

1.  문제 링크

2.  문제

요약

• 1로만 이루어진 두 자연수에 대해 최대 공약수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 두 자연수 A,B를 이루는 1의 개수가 주어집니다. 이 때, 입력되는 수는 2^63보다 작습니다.
• 출력: 첫 번째 줄에 A와 B의 최대공약수를 출력합니다.

3.  소스코드

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

public class Main {
	public long gcd(long a, long b) {
		if(b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}
	
	public long getGCD(String input) {
		StringTokenizer st = new StringTokenizer(input);
		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		long gcd = 0;
		if(a > b) {
			gcd = gcd(a, b);
		} else {
			gcd = gcd(b, a);
		}
		return gcd;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		Main m = new Main();
		long result = m.getGCD(input);
		for(int i = 0; i < result; i++) {
			bw.write("1");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 처음 접근할 때는 주어진 문제 그대로 최대공약수만을 구하려고 하였는데 주어진 숫자가 일반적인 정수 자료형으로는 풀 수 없어 규칙을 확인하였습니다.
• 이 문제는 입력에서 주어지는 두 자연수의 1의 개수에 대한 최대공약수를 구하고 그 수만큼 1을 출력하면 되는 문제입니다.
• 예를 들어, 만약 111과 1111의 최대공약수는 1이고, 1111과 11111111의 최대공약수는 1111이 되며, 1111과 111111111111이 주어졌다면 최대공약수가 1111이 될 것입니다.
• 위 예시에 있는 숫자들을 자리수로 표현해보면 3과 4의 최대공약수는 1, 4와 8의 최대공약수는 4, 4와 12의 최대공약수는 4가 됩니다.
• 즉, 주어진 두 수의 자리수에 대해 최대공약수를 구한 후, 이 수만큼의 자리수를 갖는 1로만 이루어진 자연수가 최대공약수가 됩니다.
• 최대공약수를 구할 때는 유클리드 호제법을 이용하여 최대공약수를 구하였습니다.
• GCD(a, b) = GCD(b, a % b)