[백준] 1037번: 약수

www.acmicpc.net/problem/1037

1037번: 약수

 

코드

#include <stdio.h>

main() {
	int num, tmp, div[50];	//num: 진짜 약수의 개수, tmp: 버블소트용 변수, div: 진짜 약수를 저장하는 배열
	scanf("%d", &num);
	for (int i = 0; i < num; i++)	//div에 진짜 약수 저장
		scanf("%d", &div[i]);
	for (int i = 0; i < num; i++)	//버블소트로 오름차순 정렬
		for (int j = 0; j < num - i - 1; j++)
			if (div[j] > div[j + 1]) {
				tmp = div[j];
				div[j] = div[j + 1];
				div[j + 1] = tmp;
			}
	printf("%d", div[0] * div[num - 1]);
}

 

설명

 

우선 num을 입력받고, div배열에 진짜 약수를 저장한다.

버블소트(두 개의 인접한 인덱스를 비교하여 더 큰 숫자를 뒤로 보내어 정렬)를 이용해 div배열 내의 진짜 약수를 오름차순으로 정렬한다. 어떤 숫자 n의 약수를 오름차순으로 정렬했을 때 맨 처음 약수와 맨 끝의 약수를 곱하면 n이 되는 것을 이용해, div[0]과 div[num-1]을 곱해 출력한다.