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

www.acmicpc.net/problem/1145

1145번: 적어도 대부분의 배수

 

1. 문제 설명

 

5개의 정수가 주어졌을 때 그중 3개의 정수로 나누어지는 가장 작은 배수를 구하는 문제이다.

 

첫 번째 코드는 가능한 제일 작은 배수 4에서부터 가장 큰 배수 950600(100*98*97)까지 1씩 증가해가면서 3개 이상으로 나누어지는 수가 있는지 구하는 코드이다.

 

두 번째 코드는 3개씩 쌍을 만들어 3개의 최소공배수를 구하고 3개의 최소공배수의 최솟값을 찾는 방법이다.

 

첫 번째 코드가 더 효율적인 코드인 것 같다.

 

2. 코드

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int[] movie_list=new int[5];

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

        for(int i=0;i<5;i++)
            movie_list[i]=scan.nextInt();

        System.out.println(make());


        scan.close();
    }

    public static int make(){
        int MAX=950600;
        int index=4;

        for(;index<=MAX;index++){

            int count=0;

            for(int y=0;y<5;y++){
                if(index%movie_list[y]==0)
                    count++;
            }

            if(count>=3)
                break;
        }

        return index;
    }





}

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int[] movie_list=new int[5];

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

        for(int i=0;i<5;i++)
            movie_list[i]=scan.nextInt();


        System.out.println(make());


        scan.close();
    }

    public static int make(){

        int min=1000000;

        for(int x=0;x<3;x++){
            for(int y=x+1;y<4;y++){
                
                int a=movie_list[x];
                int b=movie_list[y];

                if(a<b){
                    int temp=a;
                    a=b;
                    b=temp;
                }

                int temp_lcm=a*b/lcm(a,b);

                for(int z=y+1;z<5;z++){

                    int c=movie_list[z];
                    int d=temp_lcm;

                    if(c<d){
                        int temp=d;
                        d=c;
                        c=temp;
                    }

                    int last_lcm=d*c/lcm(d,c);

                    if(last_lcm<min)
                        min=last_lcm;

                }
            }
        }

        return min;

    }

    public static int lcm(int a,int b){

        while(b!=0){
            int r=a%b;
            a=b;
            b=r;
        }

        return a;
    }





}