Leet Code - 507. Perfect Number

예제: Perfect Number

문제
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

풀이

아주아주 쉽게 문제 설명을 하자면, 자신을 제외한 공약수들의 합이 그 자신이 되는 경우 true를 반환하는 문제이다.

문제는, 리트코드가 언제나 그렇듯이 시간이다.
모든 공약수를 더해주는 것이므로, 그 수의 제곱근까지만 공약수를 구해서 공약수 + 원래의 수 / 공약수 를 더해주면 쉽게 답을 낼 수 있다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	bool checkPerfectNumber(int num) {
		if (num <= 2) return false;

		int sum = 1;
		for (int i = 2; i < pow(num, 0.5); i++) {
			if (num % i == 0) {
				sum += i;
				sum += (num / i);
			}
		}

		return (sum == num);
	}
};

마치며

참으로 오랜만의 알고리즘 풀이이다.
그 당시 알고리즘에 얽매여 있어서 잠시 슬럼프가 왔던게 맞았던 것 같다. 이 문제를 어려워서 풀기 싫다고 생각했었다니..
물론 한참 연습했던 그때보다는 지금이 알고리즘 실력은 많이 떨어졌겠지만, 얻은것도 많다고 생각한다.
그래도 알고리즘은 꾸준히 해야지. 오늘도 마음먹어본다.