[백준] 1145번 : 적어도 대부분의 배수 – JAVA [자바]

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

 

 

---

문제

 

 

---

해결 방법

 

이 문제는 최소 공배수(LCM, Least Common Multiple) 개념을 활용하여 해결할 수 있다. 다섯 개의 수 중에서 적어도 세 개로 나누어지는 가장 작은 자연수를 찾아야 하므로, 세 개의 숫자를 조합하여 최소 공배수를 구하고, 그중 최솟값을 선택하면 된다.

문제 해결 과정

1. 다섯 개의 자연수를 입력받는다.

2. 다섯 개 중 세 개를 선택하는 모든 조합을 찾는다.

3. 선택한 세 개의 수의 최소 공배수(LCM)를 구한다.

4. 모든 조합의 LCM 중에서 최솟값을 출력한다.

최대 공약수(GCD, Greatest Common Divisor)는 두 수의 공통된 약수 중 가장 큰 값을 의미하며, 유클리드 호제법을 이용하여 효율적으로 구할 수 있다.

- GCD(a, b) = GCD(b, a % b) (b가 0이 될 때까지 반복)

- LCM(a, b) = (a * b) / GCD(a, b)

- LCM(a, b, c) = LCM(LCM(a, b), c)

최소 공배수를 구할 때 GCD를 활용하면 연산량을 줄일 수 있어 더욱 효율적인 계산이 가능하다.

이 방법을 활용하면 모든 조합의 LCM을 쉽게 구할 수 있다.

 

 

---

코드 

 

import java.io.*;
import java.util.*;

public class Main {
    // 최대공약수(GCD) 계산 함수
    public static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최소공배수(LCM) 계산 함수
    public static long lcm(long a, long b) {
        return a * (b / gcd(a, b)); // 오버플로 방지
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] numbers = new int[5];
        for (int i = 0; i < 5; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        long minLCM = Long.MAX_VALUE;

        // 5개 중 3개를 고르는 모든 조합을 순회하며 최소 공배수 계산
        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    long lcmValue = lcm(numbers[i], lcm(numbers[j], numbers[k]));
                    minLCM = Math.min(minLCM, lcmValue);
                }
            }
        }

        System.out.println(minLCM);
    }
}

 

 

---

코드 설명

1. 최대공약수(GCD)와 최소공배수(LCM) 함수 구현
- gcd(a, b): 유클리드 호제법을 이용하여 최대공약수를 구한다.
- lcm(a, b): 두 수의 최소공배수를 구하는 공식 (a * b) / gcd(a, b) 적용.

2. 입력 처리
- 다섯 개의 자연수를 배열에 저장.

3. 모든 세 개의 수 조합을 순회하며 최소 공배수 계산
- 5개 중에서 3개를 선택하는 모든 경우의 수를 찾음.
- lcm(a, b, c) = LCM(LCM(a, b), c)를 이용하여 최소 공배수를 구함.
- 모든 조합의 LCM 중 최솟값을 minLCM 변수에 저장.

4. 최솟값 출력
가장 작은 LCM 값을 출력하여 문제 해결.

---

시간 복잡도 분석

1. 5개 중 3개를 고르는 조합 개수
조합의 개수는 C(5,3) = 5! / (3!(5-3)!) = 10이다.
즉, 10번의 연산만 수행하면 되므로 작은 입력 크기에서 충분히 빠르게 동작한다.

각 조합에 대해 LCM 계산
gcd(a, b)는 O(log N)
lcm(a, b, c) = LCM(LCM(a, b), c)이므로 O(log N) 연산을 2번 수행 → O(log N)

따라서 전체 시간 복잡도는 O(10 * log N) = O(log N)으로 매우 효율적이다.