[백준] 2609 - 최대공약수와 최소공배수 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

2609번: 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,00010,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

접근방법

 최대공약수와 최소 공배수를 구하여 출력하는 문제이다. 최대공약수만 구하면, 주어진 입력에서 최소 공배수를 얻는 것은 어려운 일이 아니니, 최대공약수를 어떻게 찾을래? 가 문제의 핵심이다. 

풀이

 유클리드의 호제법을 이용하여, 문제를 해결했다. 유클리드의 호제법은 음... 두 양의 정수에서 최대 공약수를 구할 수 있는 알고리즘이다.(정확한 설명은 위키백과에서 찾아보시는 게 좋을 것 같다.) 호제법을 설명하자면 다음과 같다.

 

서로 다른 자연수 a,b 가 있을 때, a를 나눈 b를 r이라고 하자. 이때 a와 b의 최대공약수는 b와 r의 최대 공약수와 같다.

 

이 과정을 통해 나머지가 0 이 되었을 때, 나누는 수가 a와 b의 최대 공약수 이다.

 

a와 b에 대한 최대공약수를 GCD ( a, b)라고 표현했을 때, 위의 설명을 식으로 풀면 다음과 같다.

 

GCD( a, b) = GCD( b, r) = GCD ( r, r1)... = GCD(rN , 0 )

 

식으로 풀어써보니, 이해를 하기에 더욱 파멸적인 듯하여, 문제의 예제인 24와 18을 대입해보자.

 

GCD( 24 , 18) --> 나머지 r : 6

GCD( 18 , 6) ---> 나머지 r : 0

GCD( 6, 0)  ----> 나눗셈 불능

 

GCD( 24 , 18) =GCD( 18 , 6) =GCD( 6, 0)  = 6

 

 

 이렇게 보면 뭔가 신기하고, 이해가 될 듯 말 듯 했는데, 위키백과에서 증명식을 보다 보니, 한 번에 이해되었다. 나머지는 최대공약수의 배수 형태 일수밖에 없다. 이러한 성질을 이용하여, 제수(나누는 수)가 0인 부분에 피제수를 반환 값으로 하는 재귀 함수를 구현한다면 쉽게 풀 수 있다.

실패 원인

 호제법으로 풀 수 있다는 사실조차 잊고 있었다. 제한시간이 1초라길래(범위 역시 그리 크지 않고), 아무 생각 없이 반복문으로 진행했는데, 시간 초과가 아닌 의외로 '틀렸다'가 나왔다. 아마 반복문 끝 값을 '미만'으로 설정해서 나왔던 문제였다. 그래서 의도치 않게, 최대공약수를 구하는 방법을 찾게 되었고, 호제법으로 풀이를 변경했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();

    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine()," ");

        int num1 = Integer.parseInt(stk.nextToken());
        int num2 = Integer.parseInt(stk.nextToken());


        int[] answers = solution(num1,num2);

        System.out.println(answers[0]+" " +answers[1]);
    }

  private int[] solution (int a, int b){
        int gc = gcd(a,b);
        int[] result = new int[]{gc,gc*(a/gc)*(b/gc)};

        return result;
    }

      //유클리드 알고리즘
    private int gcd(int a , int b){
        // 나머지가 0 이되는 순간 다음 호출에서 리턴한다.
        if( b== 0 ){
            return a;
        }

        int mod = a % b;

        return gcd(b,mod);
    }


}

결과

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.