[JAVA] 백준 1037. 약수

이 글은 읽는데 약 4분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

입력

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

출력

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

풀이

결국 문제는 어떤 수 N의 약수를 모두 줄테니(다만 순서는 정렬되지 않을 수 있음) 원래 N을 구해라이다.

모든 약수가 주어졌기 때문에 N은 쉽게 구할 수 있다. 약수를 순서대로 정렬해서 보면 양 끝쪽에서 안으로 들어오면서 쌍을 이루며 그 곱이 N이기 때문이다.

예시로 2와 12의 곱은 24이다. 아래쪽의 3 같은 경우는 3을 두 번 곱하면 9이다.

약수의 중앙값 곱하기

내가 생각한 방법은 입력된 약수들을 정렬해서 약수의 개수에 따라 중간 쌍을 구해서 곱하는 것이었는데…

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(br.readLine());
    String[] inputs = br.readLine().split(" ");
    int[] nums = new int[T];
    for(int i=0; i<T; i++) nums[i] = Integer.parseInt(inputs[i]);

    Arrays.sort(nums);
    int result = -1;
    if(T%2 == 0){  // 약수 개수가 짝수면 -> 중앙값 두개의 곱
        result = nums[T/2 - 1] * nums[T/2];

    }else{  // 홀수면 -> 중앙값 한개의 제곱
        result = (int)Math.pow(nums[(T+1)/2 - 1], 2);
    }

    sb.append(result);
    System.out.println(sb.toString());
    br.close();
}

약수의 최소, 최대값 곱하기

다른 사람이 작성한 코드이다. 그냥 최소 최대값 구해서 곱하면 되는걸… 나는 너무 복잡하게 생각했다…

// https://www.acmicpc.net/source/8884265

public static void main(String[] ar) throws Exception{
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(in.readLine());
	StringTokenizer st = new StringTokenizer(in.readLine());
	int max = 0;
	int min = 1000000;
		
	for(int i=0; i<n; i++){
		int temp = Integer.parseInt(st.nextToken());
		if(max<temp) max = temp;
		if(min>temp) min = temp;
	}
		
	System.out.print(min*max);
}

댓글