[백준 - 1850] 최대공약수 .java

https://www.acmicpc.net/problem/1850

 

 

문제 분석

처음에 예제가 이해 안돼서 애를 먹었다.

1의 길이라는 두 수를 입력 받고 그 두 수의 최대 공약수를 구하라는게 무슨 말인지..

하지만 예제 3을 보고 알았다

단순히 길이라고 입력받은 두 수의 최대공약수를 구한다. 예제 3 경우에는 2이다.

그럼 결과는 1로 이루어진 수를 출력하면 되기 때문에 그 수의 길이는 위에서 구한 최대공약수면 된다.

문제가 너무 대충 설명한 것 같다.

 

수의 길이를 나타내는 두 수의 최대 공약수
= a, b의 최대 공약수의 길이

 

 

하지만 입력되는 수와 최대 공약수는 long 타입으로 선언해야하며

정답은 1000만 자리를 넘지 않는다는 조건 때문에 BufferedWriter를 통해 출력해야한다.

(일반적으로 하면 시간 초과)

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        //효율적인 출력 처리
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //두 개의 long 타입 숫자 입력 받음
        long a = sc.nextLong();
        long b = sc.nextLong();
        //두 숫자의 최대공약수
        long answer = gcb(a,b);

        //최대공약수의 값만큼 '1'을 출력
        for(int i = 0; i <answer; i++){
            bw.write("1");
        }
        //BufferedWriter 버퍼를 비우고 닫기
        bw.flush();
        bw.close();
    }
    //유클리드 호제법 함수
    public static long gcb(long a, long b) {
        //b가 0이 되면 a가 최대공약수
        if(b==0) return a;
        //재귀적으로 호출
        else return gcb(b, a % b);
    }
}​