Algorithm
[백준] 1037번 : 약수 (C++)
남 희
2021. 11. 23. 23:55
문제 링크
1037번: 약수
첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되
www.acmicpc.net
문제 한 줄 요약
약수를 이용해서 원래 숫자 N 구하기
풀이 (핵심 : 약수로 어떻게 N을 구할 수 있느냐를 생각해내기)
N을 가장 작은 수로 나눈다면 몫은 가장 큰 수가 될 것이다.
반대로, N을 가장 큰 수로 나눈다면 몫은 가장 작은 값이 될 것이다.
즉, 주어진 약수의 최솟값과 최댓값을 곱하면 N의 값이 나오게 될 것이다.
(단, 약수가 하나일 때는 약수의 제곱을 해준다.)
이를 이용해 다음과 같은 순서로 문제를 해결했다.
1. 입력 데이터(약수의 개수, 약수의 값) 저장하기
2. 약수 정렬하기
3. 정렬한 약수의 최소, 최대 곱한 N 출력하기