[알고리즘] 1850번

오늘 풀어볼 문제는 백준 1850번 문제 "최대공약수" 이다.

이 문제는 실버1 문제이고 정수론 문제이다.

문제

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

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

입력

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

출력

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

📌첫 번째 도전📌
최대공약수를 구하는 공식을 코드로 대입해서 문제를 풀어나갔다. 적용한 공식은 a와 b가 있을 때 a%b=c라면 b랑 c랑 다시 비교하는 것이다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long count = 0;

        while(true) {
            long c;
            if(a == 0) {
                count = b;
                break;
            }
            else if(b == 0) {
                count = a;
                break;
            }
            if(a >= b) {
                c = a % b;
                a = c;
            }
            else if(b > a) {
                c = b % a;
                b = c;
            }
        }

        for(int i=0; i<count; i++) {
            System.out.print("1");
        }
    }
}

하지만... 시간 초과가 발생했다...🌟

📌두 번째 도전📌
BufferWriter를 사용하여 시간을 줄여보기로 했다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long count;

        while(true) {
            long c;
            if(a == 0) {
                count = b;
                break;
            }
            else if(b == 0) {
                count = a;
                break;
            }
            if(a >= b) {
                c = a % b;
                a = c;
            }
            else if(b > a) {
                c = b % a;
                b = c;
            }
        }

        while(count-- > 0) {
            bw.write("1");
        }

        bw.flush();
        bw.close();
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1850