[백준 1850] - [ 수학 최대공약수 ] - 최대공약수 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/1850

---

이 문제는 어려움을 가장한 쉬운 문제이다.

낮은 정답률에 겁을 먹고 다들 시도를 하지 못한거 같다.

예제 입력 3번의 값이 이 문제는 변태적인 문제다 겁을 먹어라 하는거 같다.

500000000000000000 500000000000000002

예제 입력 1번의

3 4

로 보면 111과 1111의 최대 공약수를 구하면 되겠구나!! 하겠지만

예제 입력 3번은 어떻게 하라고.. 1을 저만치 쓰라고?? 하면서 겁을 먹게 하는거 같다.

그냥 단번에 아 낚시구나 생각했고 두 수의 최대 공약수를 구해보았다. 

예제 입력 1 의 입력값 3 4의 최대 공약수는 1

예제 입력 2 의 입력값 3, 6의 최대 공약수는 3

예제 입력 3의 입력값  무진장 큰 두 수의 최대 공약수는 고작 2

구해놓고 나니 어? 답을 구했다.

두 수의 최대 공약수만큼 1을 반복하면 되는 문제였다. 

어부지리일 수 있겠지만 머리가 빠릿빠릿하게 돌아가서 풀 수 있었던 문제인거 같긴 하다.

소스

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long num1 = sc.nextLong();
        long num2 = sc.nextLong();
        
        long gcd = getGCD(Math.max(num1, num2), Math.min(num1, num2));
        
        StringBuilder sb = new StringBuilder();
        for(int i=1; i <= gcd; i++) sb.append("1");
        
        System.out.println(sb.toString());
            
    }
    
    public static long getGCD(long a, long b) {
        while(b > 0) {
            long tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}