[BAEKJOON] 백준 기초 수학 1850 :: 최대공약수

 

💬  문제 설명

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고,
A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

 

🔨  입출력 예

입력 

• 첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

 

출력

• 첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

 

예제 입력 1)

3 4

 

예제 출력 1)

1

 

예제 입력 2)

3 6

 

예제 출력 2)

111

​

예제 입력 3)

500000000000000000 500000000000000002

 

예제 출력 3)

11

​

 

💻  Main.java

• 최대 공약수를 구하는 공식 gcd(int a, int b)를 활용해서 풀자
• 이 문제는 특이하게도 최대 공약수를 구하고, 자릿수만큼 1을 출력해줘야한다.
• System.out.print(1)으로 출력하면 시간초과가 뜸으로, StringBuilder를 사용해주자.

/* 백준 기초 수학  - 1850 :: 최대공약수 */
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();
		long max = gcd(a, b);

		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < max; i++)
			sb.append(1);
		
		System.out.println(sb);
		
		sc.close();
	}
	
	public static long gcd(long a,long b) {
		if(b == 0) return a;
		return gcd(b, a % b);
	}
}