[코드트리/NOVICE MID] 최소공배수 구하기 (JAVA)

🔺 문제

https://www.codetree.ai/missions/5/problems/find-the-least-common-multiple?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        System.out.println((n * m) / gcd(n, m));
    }
 
    // 🔔 최대공약수 구하기 (유클리드 호제법)
    private static int gcd(int a, int b) {        
        if(b == 0) return a;
        return gcd(b, a % b);
    }
}

✅ 해결 아이디어
✔ 최소공배수 = 두 숫자 곱함 / 최대공약수
- 최대공약수 구하기 => 유클리드 호제법 사용

 

 

---

🔺 다른 풀이들

다들 비슷하게 푸셨을 것 같은데

다른 분들 제출기록을 보려하니 다들 비공개를 하셨는지 안 보인다ㅎㅎ

 

---

💬 느낀 점

유클리드 호제법 오랜만에 써보다....

그래도 잊어버리면 안 된다~~

 

1회독	2회독	3회독	4회독	5회독
V