[알고리즘 문제] 백준(1145번) - 적어도 대부분의 배수

[문제]

 

문제

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

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

 

입력

첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다.

 

출력

첫째 줄에 적어도 대부분의 배수를 출력한다.

 

예제 입출력

예제 입력	예제 출력
30 42 70 35 90	210
1 2 3 4 5	4
30 45 23 26 56	1170
3 14 15 92 65	195

 

 

[문제 해설]

일단 다섯개의 자연수를 받기 위한 입력 객체를 만들면 되고, 입력 값 5개의 각각의 배수에 대한 값 중 3개 이상의 값이 같은 경우 또는 가장 작은 경우에 대한 값을 구하는 문제이다. 위의 예제 입력과 출력을 보면 자세히 알 수 있다.

핵심은 나누어 떨어질 경우 즉, 나머지가 0일 경우에 해당 배수의 값을 출력하겠다는 의미이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] numbers = new int[5];
        for (int i = 0; i < 5; i++) {
            numbers[i] = scanner.nextInt();
        }

        int candidate = 1;
        while (true) {
            int count = 0;

            for (int num : numbers) {
                if (candidate % num == 0) {
                    count++;
                }
            }
            if (count >= 3) {
                System.out.println(candidate);
                break;
            }
            candidate++;
        }
    }
}

모듈러 연산자(%)를 통해 나머지를 구하고 0일 경우에는 count++ 카운트를 증가시켜준다. 조건에 따르면 3개 이상의 배수의 값을 구해야 하므로, 카운트를 사용을 한다. count가 3개 이상일 경우 break;를 통해 반복문을 나가게 된다. 3개 이상일 경우에 나가는 이유는 또 다른 조건으로 최소값으로 구해야 하기 떄문이다. candidate는 1~?? 숫자까지 하나씩 늘어가면서 자연수의 값과 모듈러를 통해 연산을 하게 된다.