[C++] 백준 1037번 약수

1. 문제이해

1037번: 약수 (acmicpc.net)

1037번: 약수

 

1과 정수 N을 제외한 정수 N의 약수들을 입력받아,

정수 N을 구하는 프로그램을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

정수 N의 약수들 (단, 1과 자기자신은 제외) 을 입력받아 N을 구하는 것이 목표이다.

약수가 모두 주어졌으므로, 생각보다 간단한 문제이다.

 

예를 들어, 구하고자 하는 N이 18이라고 가정해보자.

18의 진짜 약수는 1과 18을 제외한 나머지 약수들, 2, 3, 6, 9 이다.

약수란, 어떤 수로 정수가 나누어떨어지는것을 대하여 이르는 말로,

18의 약수 2가 있다면 몫인 9가 있고,

반대로, 9 또한 18의 약수가 될 수 있으며, 이때의 몫은 2가 된다.

즉, 약수들을 서로 2개씩 쌍을 이루고 있으며, 이 한 쌍의 약수들을 곱하면 바로 해당 정수값이 나오게 된다.

즉, 위의 경우인 18에서는 2와 9, 3과 6이 서로 쌍을 이루고 있으며,

해당 값들을 곱하면 18이 나오게 된다.

 

그렇다면, 이 쌍을 어떻게 구하여 곱해야 할까?

간단하다. 바로, 정렬을 해주면 된다.

정렬을 해준 뒤, 약수들 중 가장 작은 값 x 가장 큰 값을 해주게 되면 N을 구할 수 있다.

(약수들 중 n번째로 작은 값 x n번째로 큰 값을 해주어도 같은 결과를 얻을 수 있다.)

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int num;            // 약수의 개수
	int divisor[50];    // 약수
	int N = 0;          // 입력받은 약수를 가진 정수  

	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> divisor[i];
	}

	sort(divisor, divisor + num);

	// 약수들 중 가장 작은 값 x 가장 큰 값을 해주면 N
	N = divisor[0] * divisor[num - 1];
	cout << N;

	return 0;
}

2. 문제풀이에서 도출한 풀이방법에 착안하여 위와 같이 코드를 작성했다.

약수의 개수와 약수들을 입력받고, 해당 약수들을 정렬했다. (오름차순)

N은 약수들 중 가장 작은 값 x 가장 큰 값과 같으므로, 위와 같이 계산 후 출력해주었다.

 

 

---

개인적인 사정으로 인해 일주일동안 쉬다 왔습니다..🙏

이제 다시 열심히 블로그 가꾸고, 밀린 공부도 해야지💪