[백준 C++] 1037 약수

cldhfleks2·2021년 11월 21일
0

문제

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

입력

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

출력

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

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

풀이

중요한점은 최대입력횟수가 백만회인데,
C/C++에서 int형배열의 최대크기는 십만정도이다.
따라서 모든 값을 배열에 저장하려는것은 애초에 비효율적인 접근이었고, 약수의 특성을 활용하면된다.
모든 약수가 주어지므로,
약수는 양끝값을 곱하면 해당 N이 되므로.
예로들면 n = 16 이면
2, 4 ,8약수중
2 x 8 = 16
4 x 4 = 16 이므로
이를 간단히 보자면 입력값중의 최솟값, 최댓값을 찾아서 서로를 곱하면 N이된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>

int main(void) {
	int T, min=0x7fffffff, max = 0;
	scanf("%d", &T);
	if (T == 1) {
		int temp=0;
		scanf("%d", &temp);
		printf("%d", temp * temp);
	}else{
		while (T--) {
			int temp;
			scanf("%d", &temp);
			if (min > temp)
				min = temp;
			if (max < temp)
				max = temp;
		}
		printf("%d", min * max);
	}
	return 0;
}

여기서 0x7fffffff 은 int최댓값을 16진수로 표기한것

profile
i will be a developer

0개의 댓글