https://www.acmicpc.net/problem/9506
9506번: 약수들의 합
어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.
www.acmicpc.net
문제 해결 과정
착안
주어진 수 \(n\)의 약수를 구하기 위해서는 \(i = 1\)부터 최대 \(i = \sqrt{n}\) 까지의 자연수로 나누어보면 모든 약수를 구할 수 있다(\(a\)가 \(n\)의 약수이면, 반드시 \(n/a\)도 \(n\)의 약수이기 때문이다). 이를 이용해 약수를 구하는 과정의 시간 복잡도를 \(O(\sqrt{n})\)으로 단축시킨다.
구현
위와 같이 문제를 해결하면 약수의 순서가 뒤죽박죽으로 섞이기 때문에 모든 진약수(proper divisor)를 구한 다음, 문제에서 약수를 오름차순으로 정렬하는 것을 요구하는 것과 같이 정렬한다.
정렬 알고리즘은 직접 구현할 수 있지만, 이 문제에서는 정렬 알고리즘을 직접적으로 요구하지 않았기 때문에 STL algorithm 헤더에 포함된 sort 함수를 이용하여 정렬하였다(sort 함수가 STL의 컨테이너에만 적용할 수 있는 건 아니지만 마침 약수의 개수를 미리 알 수 없으므로 약수를 저장할 컨테이너로 STL vector 클래스를 이용한 점도 있다).
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n = 0;
vector<int> factors = { 1 };
while (true)
{
cin >> n;
if (n == -1)
break;
int sum_factors = 1;
for (int i = 2; i <= sqrt(n); i++)
{
if (!(n % i))
{
// i is a factor
factors.push_back(i);
sum_factors += i;
if (n / i != i)
{
// factor pair
factors.push_back(n / i);
sum_factors += (n / i);
}
}
}
sort(factors.begin(), factors.end());
cout << n;
if (sum_factors == n && n > 2)
{
// perfect number
cout << " = ";
for (int factor : factors)
{
cout << factor;
if (factor != factors.back())
cout << " + ";
}
}
else
{
// not perfect number
cout << " is NOT perfect.";
}
cout << endl;
factors.clear();
factors.push_back(1);
}
return 0;
}
실행 결과
* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 1010번: 다리 놓기 (0) | 2023.05.06 |
---|---|
[Baekjoon] 2581번: 소수 (0) | 2023.05.06 |
[Baekjoon] 5086번: 배수와 약수 (0) | 2023.05.06 |
[Baekjoon] 1193번: 분수찾기 (0) | 2023.05.06 |
[Baekjoon] 2292번: 벌집 (0) | 2023.05.06 |
댓글