[백준 - 1037][Java] 약수

이 포스팅은 자바 8버전으로 풀이가 됐습니다.

 

 

 

문제

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

입력

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

출력

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

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
// 1037번
public class Main {
    public static void main(String[] args) throws IOException {
        try {
            BufferedReader rd = new BufferedReader(new InputStreamReader (System.in));
            
            int N = Integer.parseInt(rd.readLine());
            String text[] = rd.readLine().split(" ");
            int A[] = new int[N];
            
            for(int i=0;i<N;i++) {
                A[i] = Integer.parseInt(text[i]);
            }
            Arrays.sort(A);
            System.out.print(A[0]*A[A.length-1]);
        }
        catch(IOException e) {
            System.out.println("error");
        }
    }
}

풀이

이 문제를 풀이하기 위해서는 약수를 원리에 대하여 역으로 값을 접근하면 구할 수 있다.

우선 간단하게 약수를 언급한다.

약수란? 어떤 변수를 나누어 떨어지게 하는 수를 말하는 것이다.

16의 약수는 다음과 같다.

처음 시작하는 값과 끝의 값을 곱하면 1*16 = 16이 나온다. 그리고는 2*8=16, 4*4=16이 나온다.

다시 본론으로 돌아간다.

이 문제에서는 1과 구하려는 N의 값이 아니어야 하는 조건이 있다.

그러므로 1*16 = 16은 존재하지 않는다.

홀수의 경우 또는 짝수의 경우 처음 값과 끝 값 -1에 위치한 곱하면 원래 값을 알 수 있다.

 

이 문제의 핵심은 "약수를 알면 원래 값을 알아낼 수 있다."이다. 그렇다면 이 문제는 약수를 곱하여 원래 값을 찾아내는 것이다. 다른 다양한 풀이들이 존재할 수 있지만 최근에 정렬을 복습할 때 배웠던 Arrays.sort()를 사용하여 문제를 하려 하므로 다음과 같이 풀이를 진행할 수 있다.

Arrays.sort() 함수는 배열을 오름차순으로 정렬할 수 있다.

입력에서 4 8 2를 넣으면 Arrays.sort(배열 변수)는 오름차순으로 정렬 -> 2, 4, 8의 값을 갖는다.

이때 0번 배열은 2 끝에 존재한 배열의 값은 8을 갖는다.

이를 곱하면 2*8=16으로 16의 약수를 찾을 수 있게 된다.

 

 

---

짧은 포스팅 읽어주셔서 감사드립니다. 오타나 문제가 있는 경우 댓글 부탁드리겠습니다.

감사합니다. 다음 포스팅 때 뵙겠습니다.