[백준] 1037번: 약수_Java

 

제목:약수

실버5

---

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

---

아직 초보자인 나한테는 조금 시간도 걸리고 어려워서 인터넷을 서칭해서 풀긴 했다.

 

 

코드리뷰: A[]배열에다가 사용자가 입력한 값 N을 넣는다. 그럼 A[]배열의 길이가 만들어질 것이다.

             for문에서 사용자에게 약수 중간 값을 입력 받는다.

             Arrays.sort(A)로 A[]배열을 내림차순으로 정렬한다.

             정렬된 배열에서 최소공약수  A[0]* 최대공약수 A[N-1]을 한다  (A[I]*A[N-1]) 

             여기서, A[N-1]은 A index값은 0부터 시작하므로 최대값을 참조하기 위해서는 -1를 해야한다.

 

핵심: 문제를 풀기 위해서 배열정렬에 대해 공부해야한다.

       또한 약수의 중간값에서 최소 공약수 * 최대 공약수 = 구하고자 하는 양수

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		int[] bit=new int[N];
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			bit[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(bit);
		System.out.println(bit[0]*bit[N-1]);
	}
}

 

BufferedReader 클래스 사용

 

 

 

 

 

 

알고리즘 분류

• 수학
• 정렬
• 정수론

 

 

https://www.acmicpc.net/problem/1037

1037번: 약수

 

 

 

 

 

커버사진

https://www.flaticon.com/kr/free-icon/algorithms_1753819

 

<a href="https://www.flaticon.com/kr/free-icons/" title="연산 아이콘">연산 icons created by Flat Icons - Flaticon</a>