[BOJ] 백준 1037 약수

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

Approach

진짜 약수 의미를 고려하면 쉽게 구현할 수 있다.

ex) A = 20 일 때, 20의 약수는 [1, 2, 4, 5, 10, 20] 이다.

    이때, 진짜 약수는 [2, 4, 5, 10]인데 → (2 × 10) 혹은 (4 × 5)

여러 약수 조합 중에서 최소값과 최대값에 해당되는 원소로 곱해주면 된다.

 

주어지는 진짜 약수를 배열에 저장해서 정렬한 뒤, → sort() 이용

첫번째/마지막 원소가 최소값/최대값에 해당된다.

 

구현할 때, 진짜 약수가 1개인 경우도 주의해야 한다.

ex) 9의 진짜약수는 [3] 이기 때문에 최소/최대값이 동일하다.

(32비트 부호있는 정수 조건이므로 int 표현이 가능하다.)

 

C++

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 50 + 2;
int N, arr[MAX_N];
int main() 
{
	// freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", arr + i);
	}

	sort(arr, arr + N);

	// 최소값 * 최대값
	cout << arr[0] * arr[N - 1] << endl;
}

 

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = Integer.parseInt(sc.next());
        
        List<Integer> list = new ArrayList<>();
        
        while(T-- > 0) {
        	list.add(Integer.parseInt(sc.next()));
        }
        
        Collections.sort(list);
        
        int max = list.get(list.size()-1);
        int min = list.get(0);
        
        System.out.println(max * min);
    }
}