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

# 주소

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

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

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = scan.nextInt();
        int y = scan.nextInt();
        int gcd = 0;
        if(x >= y) {
        	System.out.println(gcd(x,y));
        	gcd = gcd(x,y);
        }
        else {
        	System.out.println(gcd(y,x));
        	gcd = gcd(y,x);
        }
		System.out.println((x * y)/gcd);
    }
    public static int gcd(int a, int b){
        while(true){
        	int r = a;
            a = b;
            b = r % b;
            if(b == 0) {
            	break;
            }
        }
        return a;
    }
}

 

단순히 최대공약수와 최소공배수를 구하려고 했으나, 자꾸만 시간초과가 떠서 다른 방법을 생각해야 했습니다.

검색을 하던 중 정수론 과목의 유클리드 호제법이 자주 언급되었고 주변 지인에게 부탁해 정수론 책의 사진을 받았습니다.

저도 전공이 수학교육과라서 정수론을 들었지만(심지어 A학점이었는데) 군입대 하기 전이라 그런지 까먹고 있던

개념이었습니다..  그 내용대로 풀이하니 확실히 간단한 문제였습니다.

이런 내용인데, 한마디로 gcd(a,b)를 입력 받으면 gcd(b , a%b)와 같아진다는 내용입니다.

코드에서 볼 수 있듯이 a와 b를 적절하게 바꾸어 주면서 gcd의 b값이 0이 될 때 a값을 return해주어

원하는 gcd값을 얻을 수 있습니다.

주의해야할 것이 처음에 이렇게 코딩을 입력했는데도 마지막에 틀렸다고 떠서 뭘까... 고민하던 찰나에

입력받는 x와 y의 크기 순서에 따라 gcd값이 바뀔 수 있음을 확인하였고 때문에 x와 y의 대소관계에 따라

gcd를 정의하니 간단히 해결되었습니다.

감사합니다.