공부 94일차: 백준 2609번 최대공약수와 최소공배수 자바 java

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

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

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

 

 

 

---

백준 2609번 문제 최대공약수와 최소공배수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

두 숫자 모두 소인수분해한 뒤 최소공배수와 최대공약수를 구해보려고 했는데..

두 숫자가 공통으로 가지는 소인수를 구하려면 또 ArrayList같은 곳에 저장하고 같은지 비교해야 하는데 

그러면 시간이 너무 오래 걸릴 것 같았다

 

그래서 백준 문제에서 알고리즘 분류를 눌러보니 '유클리드 호제법'이라는 게 있어서 찾아보았다

알고리즘을 제대로 공부한다면 꼭 만나게 되는 개념인 듯했다

 

https://gimbalja.tistory.com/410

유클리드 호제법 (최대공약수와 최소공배수)

여기에 정리해두었다

 

 

 

---

정답 인정 코드

---

 

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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int first = Integer.parseInt(st.nextToken());
        int second = Integer.parseInt(st.nextToken());
 
        //유클리드 호제법
        int gcd = gcd(first, second);
        int lcm = first * second / gcd;
        System.out.println(gcd);
        System.out.println(lcm);
    }
 
    public static int gcd(int x, int y) {
        if(y == 0)
            return x;
        else
            return gcd(y, x%y);
    }
}
 

 

특정 알고리즘이 유명하다는 건, 남들도 다 알고 있다는 뜻일 것이다

외워두기!

 

 

 

---