본문 바로가기

컴퓨터/백준 알고리즘

백준 알고리즘 1037번: 약수 [C++]

문제 출처: www.acmicpc.net/problem/1037

 

1037번: 약수

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

www.acmicpc.net

1. 코드

#include <iostream>

using namespace std;

int main(void)
{
	int N;
	int big = 0;
	int small;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		if (i == 0) small = num;
		if (num > big) big = num;
		if (num < small) small = num;
	}
	cout << big * small;
	return 0;
}

(실행)

2. 풀이

문제를 읽어보면 약수의 갯수를 입력하고 약수들을 입력한다고 나왔있는데 이 때 입력되는 약수의 갯수는 1과 해당하는 수의 갯수가 제외된 수 즉, 8일 경우 약수는 4개가 아닌 2개인 것이다. 그리고 1과 자기자신을 제외하기 때문에 약수들이 어떤 수의 약수인지 확인하기 쉬운데 그 방법은 약수들 중 가장 큰 값과 가장 작은 값을 곱한 값이다.

예를 들어서 8일 경우 (1, 2, 4, 8)이 약수인데 문제에서는 1과 8을 제외한 (2, 4)를 입력하는데 이 두 개의 곱은 8로 이렇게 정답을 구할 수 있다. 만약 애매하다고 느껴진다면 한번 24를 예를 들어 설명해보겠다. 24의 약수는 (1, 2, 3, 4, 6, 8, 12, 24) 그리고 문제에서는 1과 24를 제외한 (2, 3, 4, 6, 8, 12)를 입력한다. 그리고 입력된 값 중 가장 작은 값인 2와 가장 큰 값인 12를 곱하면 24를 구할 수 있다.

3. 느낀 점

문제에 대해서 잘 이해하고 수들의 관계에 대해 빠르게 파악할 수 있다면 쉬운 문제이다.