99클럽 코테 스터디 35일차 - 완전탐색

문제

적어도 대부분의 배수

풀이

• 주어진 5개의 자연수 중 적어도 3개로 나누어 떨어지는 가장 작은 수를 구해야함
• 즉, 3개 조합의 최소공배수의 최소값
• for문 3번 중첩해서 순회하면서 모든 경우 구하고 각각 최소공배수도 구해줌

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums = new int[5];
        
        for (int i = 0; i < 5; i++) {
            nums[i] = scanner.nextInt();
        }
        
        int answer = Integer.MAX_VALUE;
        
        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    int lcm = lcm(nums[i], lcm(nums[j], nums[k]));
                    answer = Math.min(answer, lcm);
                }
            }
        }
        
        System.out.println(answer);
    }
    
    // 최대공약수 
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
    
    // 최소공배수
    private static int lcm(int a, int b) {
        return a * (b / gcd(a, b));
    }
}

정리

• 최소공배수, 최대공약수 구하는 거 까먹어서 인터넷 봄...