[JAVA] 8. 필수 알고리즘 Ⅳ. 최소공배수(LCM)

최재원

Feb 08, 2025

Contents

1. 최소공배수 알고리즘(LCM)2. 놀이공원 회전 놀이기구 최소공배수로 해결하기 3. 둘은 몇시에 만나는가?

💡

두 수의 곱을 두 수의 최대공약수로 나누면, 그 수가 최소공배수다.

1. 최소공배수 알고리즘(LCM)

❗

4와 9의 최소 공배수를 구하여라.


4의 배수 : 4,8,12,16,20,24,28,32,36
9의 배수 : 9,18,27,36

최소 공배수는 36


package algo;

public class Lcm {
    public static void main(String[] args) {
        // 4와 9의 최소공배수를 구하여라.
        // LCM(4,9) = 4 * 9 / GCD(4,9)

        int a = 4;
        int b = 9;

        int lcm = a * b / Gcd.gcd(a, b);
        System.out.println(a + "와 " + b + "의 최소공배수는 " + lcm);
    }
}

2. 놀이공원 회전 놀이기구


관람차 A는 15분마다 한 바퀴 회전
관람차 B는 20분마다 한 바퀴 회전
두 관람차가 동시에 원래 위치로 돌아오는 최소 시간은?

최소공배수로 해결하기

정답


package algo;

public class Lcm {
    public static void main(String[] args) {
        // 관람차 A는 15분마다 한 바퀴 회전
        // 관람차 B는 20분마다 한 바퀴 회전
        // 두 관람차가 동시에 원래 위치로 돌아오는 최소 시간은?
        
        // A관람차 15, 30, 45, 60
        // B관람차 20, 40, 60

        // 1. 변수 생성
        int a = 15;
        int b = 20;

        // 2. 관람차 A와 관람차 B의 최소공배수 구하기
        int lcm = a * b / Gcd.gcd(a, b);

        // 3. 두 관람차가 동시에 원래 위치로 돌아오는 최소시간 출력
        System.out.println("최소시간: " + lcm + "분");
    }
}

3. 둘은 몇시에 만나는가?


A는 10시에 출발하여 40km/h의 속도로 이동
B는 11시에 출발하여 60km/h의 속도로 이동
몇시에 만나는가?

정답


package algo;

public class Lcm {
    public static void main(String[] args) {
        // A는 10시에 출발하여 40km/h의 속도로 이동
        // B는 11시에 출발하여 60km/h의 속도로 이동
        // 몇시에 만나는가?

        // A의 도착시간 : 40,  80,  120, 160,  200
        //             11시, 12시, 13시, 14시, 15시
        // B의 도착시간 :  0,  60,  120, 180,  240

        int aStart = 10;
        int bStart = 11;

        int aSpeed = 40;
        int bSpeed = 60;

        // 1. A와 B의 만나는 이동거리 = 최소공배수
        int lcm = aSpeed * bSpeed / Gcd.gcd(aSpeed, bSpeed);

        // 2. 공통된 이동거리를 속도로 나눈다.
        int aHour = lcm / aSpeed;
        int bHour = lcm / bSpeed;

        // 3. 도착시간을 구한다.
        System.out.println("A는 " + lcm + "거리를 이동하는데 " + aHour + "시간 걸린다. 도착시간은 " + (aStart + aHour) + "시이다.");
        System.out.println("B는 " + lcm + "거리를 이동하는데 " + bHour + "시간 걸린다. 도착시간은 " + (bStart + bHour) + "시이다.");


    }
}

See more posts

[JAVA] 8. 필수 알고리즘 Ⅳ. 최소공배수(LCM)

1. 최소공배수 알고리즘(LCM)

2. 놀이공원 회전 놀이기구

최소공배수로 해결하기

정답

3. 둘은 몇시에 만나는가?

정답

More articles

[JAVA] 8. 필수 알고리즘 Ⅵ. 서로소

[JAVA] 8. 필수 알고리즘 Ⅴ. 소수 판별

[JAVA] 8. 필수 알고리즘 Ⅲ. 최대공약수(GCD)

[JAVA] 8. 필수 알고리즘 Ⅱ. 약수 구하기