JuSeok

1145번

문제

다섯 개의 자연수가 있다. 이 수의 적어도 대부분의 배수는 위의 수 중 적어도 세 개로 나누어 지는 가장 작은 자연수이다.

서로 다른 다섯 개의 자연수가 주어질 때, 적어도 대부분의 배수를 출력하는 프로그램을 작성하시오.

문제 해결 순서

  1. 다섯 개의 자연수 중에서 적어도 3개의 자연수의 최소공배수 중 가장 작은 수를 구하는 문제.
  2. 유클리드 호제법을 사용해 최대공약수와 최소공배수를 구하는 함수를 만듦.
  3. 브루트 포스로 모든 경우의 수를 탐색하며 가장 작은 최소공배수를 구해냄.
import java.util.Scanner;

public class test2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int min = Integer.MAX_VALUE;

        // 배열에 수 입력
        int arr[] = new int[5];
        for (int i = 0; i < 5; i++){
            arr[i] = scan.nextInt();
        }

        // 브루트포스
        for (int i = 0; i < 5; i++){
            for (int j = i + 1; j < 5; j++){
                for (int k = j + 1; k < 5; k++){
                    // 3가지 수에 대한 최소공배수 구하기
                    int temp = lcm(arr[i], lcm(arr[j], arr[k]));
                    if (min > temp){
                        min = temp;
                    }
                }
            }
        }

        System.out.println(min);
    }
    // 최대공약수
    static int gcd(int a, int b){
        while(b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

    // 최소공배수
    static int lcm(int a, int b){
        return a * b / gcd(a, b);
    }
}

Tags