[백준(BaekJoon)] 1850 : 최대공약수 - JAVA(자바)

# 문제

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

1850번: 최대공약수

# 풀이 과정

• 유클리드 호제법으로 최대 공약수를 구했다(MOD 연산)

static long euclidean(long a, long b) {
    //1.두 수의 나머지 값을 구한다
    long rest = a % b;
    //2. 나머지 값이 0이 될 때까지 아래의 연산을 반복한다
    while(rest != 0) {
        long save = rest;
        rest = b % rest;
        b = save;
    }
        return b;
}

• 맨 처음 두 자연수 a와 b의 나머지 값을 구한다
• 이 때 나머지 값이 0이 아닌 경우 0이 될 때까지 mod 연산을 반복해준다
• 새롭게 구하는 나머지 값 = 전 단계에서의 두 숫자 중에 작은값(다음 단계의 큰 값) % 전 단계에서 계산한 두 숫자의 나머지 값(다음 단계에서의 작은 값)
• 나머지가 0이 되는 경우 나머지를 0으로 만든 마지막으로 연산한 두 숫자 중에 작은 값이 최대공약수가 된다

# 전체 코드

import java.util.Scanner;

public class Main {
    static long euclidean(long a, long b) {
        //두 자연수 a와 b의 나머지 값
        long rest = a % b;
        //나머지 값이 0이 될 때까지 반복한다
        while(rest != 0) {
            //새로운 나머지 값 = 전 단계의 작은 값 % 전 단계에서의 연산 결괏값(나머지값)
            long save = rest;
            rest = b % rest;
            b = save;
        }
        //나머지 값을 0으로 만든 두 숫자 중에 작은 값이 최대공약수
        return b;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        //두 자연수 입력
        long A = sc.nextLong();
        long B = sc.nextLong();

        long gcd;
        
        //큰 수를 작은 수로 나눠야 되기 때문에 A와 B의 크기에 따라 달리 실행해준다
        if(A > B) gcd = euclidean(A, B);
        else gcd = euclidean(B, A);

        for(int i = 0; i < gcd; i++) {
            sb.append(1);
        }
        System.out.println(sb);
    }
}

# 결과