[백준 BOJ] 1037번 약수 (C++/cpp)

문제 설명

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

1037번: 약수

 

접근 방법 - 정렬 함수 사용의 기본 문제

백준의 1037번 문제는 정렬 함수 sort()를 사용하여 해결할 수 있는 문제이다.

해당 문제는, 1과 n이 아닌 n의 약수들을 입력받아서 n을 추측하여 이를 출력해야 하는 문제이다.

사실 해당 문제의 알고리즘 분류에는 정렬 개념이 없다.

하지만 약수들은 결국 알맞은 한 쌍씩 곱하면 약수들의 주인인 숫자가 나타나기 마련이다.

따라서 필자는 정렬을 사용한다면 해당 문제를 더욱 용이하게 풀 수 있음을 발견하였고 이를 기반으로 코드를 작성하였다.

(추가적으로, 입력값들 중 최댓값 및 최솟값을 구하여 해결할 수 있는 방법도 있음을 알리고 싶다.)

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력받을 약수들을 저장할 배열(arr)을 전역 변수로 선언한다.

 

2) 약수의 개수(n)와 약수들을 입력받는다.

 

3) sort() 함수로 arr의 배열값들을 정렬한다.

 

4) 3)의 정렬이 끝나는 대로, arr의 첫번째 값과 마지막 값을 곱한 값을 출력한 뒤 실행 종료한다.

(arr 배열값들 중 최솟값과 최댓값을 곱한 값이 우리가 구하고자 하는 n의 값이 될 것이다.

여기서 배열값들을 오름차순으로 정렬하고 나면, 배열의 첫번째 값이 최솟값이며 배열의 마지막 값이 최댓값이 될 것이다.)

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 1037번 코드
int arr[1000000];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	cout << arr[0] * arr[n - 1] << endl;
}

 

제출 결과

(2022.05.02 백준 1037번 문제 제출 결과)