[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)1145번, 적어도 대부분의 배수

문제 링크

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

---

 

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 서로 다른 자연수 5개가 주어집니다.

2. 대부분의 배수는 5개의 자연수에서 최소 3개 이상 나누어떨어지는 가장 작은 수입니다.

3. 대부분의 배수를 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 자연수 최소값부터 탐색을 진행하여 대부분의 배수의 만족하는지 탐색합니다.

 

3. 대부분의 배수를 결과로 출력합니다.

 

 

대부분의 배수 탐색

 

자연수 최소값부터 증가하면서 주어진 서로 다른 5개의 자연수의 나누어 떨어지는 지 확인합니다.

※최소값부터 탐색하는 이유 : 최소값보다 작으면 나누어 떨어지는 수가 존재하지 않습니다.

 

3개 이상 나누어 떨어지지 않을 때

자연수 = 자연수 + 1

 

3개 이상 나누어 떨어졌을 때

대부분의 배수 발견!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

30

42

70

35

90

 

2. 자연수 최소값부터 탐색을 진행하여 대부분의 배수의 만족하는지 탐색합니다.

자연수 최소값 : 30

 

30부터 대부분의 배수의 만족하는지 탐색

 

30 : 나누어 떨어지는 수 = 30

 

31 : 나누어 떨어지는 수 = X

 

32 : 나누어 떨어지는 수 = X

 

33 : 나누어 떨어지는 수 = X

 

34 : 나누어 떨어지는 수 = X

 

35 : 나누어 떨어지는 수 = 35

....

210 : 나누어 떨어지는 수 = 30, 42, 70

 

대부분의 배수 : 210

 

3. 대부분의 배수를 결과로 출력합니다.

 

210을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 사용하여 서로 다른 5개의 자연수를 띄어쓰기 기준 나누었습니다.
• 최소값부터 대부분의 배수의 만족하는지 탐색합니다.
• 탐색으로 찾은 대부분의 배수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] num = new int[5];
        int n = Integer.MAX_VALUE;
        //서로 다른 5개의 자연수 저장 및 최소값 구하기
        for(int i=0;i<5;i++){
            num[i] = Integer.parseInt(st.nextToken());
            n = Math.min(num[i], n);	//최소값 구하기
        }
        //최소값부터 대부분의 수 조건 만족하는지 탐색
        while(true){
            int count = 0;	//나누어떨어지는 개수 변수
            for(int i=0;i<5;i++){
                if(n % num[i] == 0)	//나누어 떨어질 때
                    count++;
                if(count == 3)
                    break;
            }
            if(count == 3)	//3개 이상 나누어 떨어지면 탐색 종료
                break;
            n++;
        }
        bw.write(n + "");	//대부분의 수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}