[백준/Java] 적어도 대부분의 배수 1145 (뇌빼기 연습)

(*뇌 빼기 프로젝트 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자)


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

 

 

조건

• TimeLimit = 2s
• n = 5
• 각 수는 100이하의 서로 다른 자연수

 

 

풀이

1. 자연수가 5개밖에 없으니까, 모든 조합(5C3)을 구한 다음 최소공배수를 구해도 가능하겠다
   -> nCr 어떻게 구현?
   -> 아! 재귀로 구현해보자 ...
   
   
2. 더 간단하게 가능?
   -> 재귀는 무슨, 그냥 3중 for문 돌려버려도 되지 않나?
   -> 최소공배수를 구하려면 이건 불가능
   
   
3. 더 간단하게 가능??
   -> 생각해 보면 가능한 최댓값이 98*99*100(대략100만)임
   -> 이 말은, 1부터 대략 100만까지 전부 다 탐색해도 O(100만)이므로, 2s기준인 2억에 한참 못 미침
   -> 따라서 아주 단순하게 1부터 100만까지 전부 탐색하자!
   • 여기서 최소 3개의 배수가 되는 건 어떻게 해결할래? 아까처럼 조합 구할 거야?
     -> 아니. 그러지 말고, 그냥 5개의 수를 전부 각각 n으로 한 번씩 나눠보면 됨
     -> 나눠지면 cnt ++하고, 최종적으로 cnt >=3이면 정답임

 

 

 

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
        
		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] input = Arrays.stream(br.readLine().split(" "))
				.mapToInt(Integer::parseInt)
				.toArray();
		
		// find min num
		for (int i=1; i<=98*99*100; i++) { 
			int cnt = 0;
			for (int j: input) {
				if (i%j == 0) {
					cnt ++;
				}
			}
			if (cnt >= 3) {
				System.out.print(i);
				return;
			}
		}
    }
	
}