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

https://www.acmicpc.net/problem/1145
이 문제는 완전 탐색 알고리즘을 사용하는 문제이다. 즉, 모든 경우의 수를 전부 탐색해야 한다.

처음에는 3중 for문을 이용하여 각각의 for문에서 꺼내는 배열 요소가 min값으로 나누어지면 다음 요소로 넘어가서 확인하도록 로직을 작성하였다.

하지만, 이는 시간복잡도가 O(n^3)으로 매우 비효율적이며, 단순히 '개수'만 세어주면 되므로 그냥 while문을 사용하면 되는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        //적어도 대부분의 배수 : 적어도 세 개로 나누어 지는 가장 작은 자연수
        //주어지는 다섯 개의 자연수 모두 100보다 작으므로 1씩 증가시켜서 모든 수를 따져도 괜찮음
        int length = input.length;
        int min = 1;
        while (true) {
            int cnt = 0;
            for (int i = 0; i < length; i++) {
                if (min % Integer.parseInt(input[i]) == 0) { //나누어 떨어지는 수이면
                    //적어도 3개만 있으면 되므로 하나하나의 요소를 검사해주면 됨
                    cnt++;
                    if (cnt == 3) {
                        break;
                    }
                }
            }
            if (cnt == 3) {
                break;
            }
            min++;
        }
        System.out.println(min);
        br.close();
    }
}