[BaekJoon Silver3] C++: 이면수와 임현수

그동안 하루에 한 문제 이상씩 알고리즘 문제를 계속 풀어오긴 했지만, 블로그로 정리하지는 못했다. 오늘 풀 문제는 문제 길이부터가 어마어마하게 길어서 정리하지 않고는 풀기 힘들 것 같아 다시 블로그를 작성하게 되었다. 

문제 링크: https://www.acmicpc.net/problem/1291

문제 분석

Input: 

• input: 문제에서 주어진 방식으로 분석해야 되는 자연수

Output: 

• result: 분석 결과
  • 1: 이면수 - (4 or 6 이상의 수) and (각 자릿수의 합이 홀수)
  • 2: 임현수 - (2 or 4) or (합성수 and 소인수의 개수가 짝수인 수)
  • 3: 성경수 - 이면수도, 임현수도 아닌 수.
  • 4: 이면수 & 임현수

` 완벽한 숫자와 태초의 숫자들(2와 3)의 합` 이라는 absolute의 조건에서 완벽한 숫자라는 말이 처음에 나에게 혼동을 주었다.

• 1: 위대한 숫자
• 2: 태초의 짝수
• 3: 완벽한 태초의 수
• 4: 완벽한 숫자

위의 분류에 따라 해석하자면: 
해석1: 완벽한 숫자(4) + (태초의 짝수(2) 또는 완벽한 태초의 수(3) 들의 합)
해석2: 완벽한 숫자(3 또는 4) 와 태초의 숫자 (2 또는 3) 들의 합

나는 이렇게 2가지 해석의 여지가 있다고 보았다. 단어의 조합 그대로 해석하자면 2번이 더 합리적인 것 같지만, ` 3가지 분류방법에 모두 들어가지 않는 숫자인 5` 라는 조건이 2번 해석으로는 들어맞지 않게 된다.

absolute인 것이 확실한, 4를 제외한 나머지 수들을 해석1대로 분석하자면:
6 = 4 + 2
7 = 4 + 3
8 = 4 + (2 + 2)
9 = 4 + (2 + 3)
10 = 4 + (3 + 3)

이처럼 모든 수가 해석 1의 조건에 맞는 것을 확인할 수 있다. 사실 4는 2의 2배라 5를 예외로 하고 <2 또는 3들의 합>으로 해석해도 같은 결과가 나오지만, 문제의 의도를 정확하게 분석하고 싶었다.

다음으로, 임현수의 조건도 (2 or 4) or (합성수 and 소인수의 개수가 짝수인 수) 인지 (2 or 4 or 합성수) and (소인수의 개수가 짝수인 수) 인지에 따라서도 달라졌다. 이 부분은 맨 밑의 11->3 이라는 결과 해석에서 근거를 찾아야만 했다.

문제 풀이

초안

소요시간: 약 1시간.
조건 하나를 잘못 읽어서 조금 헤맸다.

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

bool isA(int num);
int digitSum(int num);
bool isB(int num);
bool isPrime(int num);
bool evenPrimeFactor(int num);

enum NumType {
	i_myeon = 1,
	im_hyeon,
	sung_gyeong,
	both
};

int main() {
	int input;
	cin >> input;

	NumType result;
	if (isA(input)) {
		if (isB(input)) {
			result = both;
		} else {
			result = i_myeon;
		}
		
	} else if (isB(input)) {
		result = im_hyeon;
	} else {
		result = sung_gyeong;
	}

	cout << result << endl;
}

/*이면수인가?
absoulte인가 = 4 또는 6 이상의 모든 자연수.
and
각 자릿수의 합의 홀수인가.
*/
bool isA(int num) {
	if (num < 6 || num != 4) return false;
	return digitSum(num) % 2 != 0;
}

/*각 자릿수의 합*/
int digitSum(int num) {
	int sum = 0;
	while (num != 0) {
		sum += num % 10;
		num /= 10;
	}
	return sum;
}

/*임현수인가?
2 또는 4.
or
합성수 and 소인수의 종류가 짝수개.
*/
bool isB(int num) {
	if (num == 2 || num == 4) return true;
	if (num < 4) return false;

	if (!isPrime(num) && evenPrimeFactor(num)) return true; 
	return false;
}

/*소수인가*/
bool isPrime(int num) {
	if (num <= 1) return false;
	if (num == 2) return true;
	if (num % 2 == 0) return false;

	for (int i = 3; i <= sqrt(num); i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

/*소인수의 개수가 짝수인가*/
bool evenPrimeFactor(int num) {
	set<int> primeFactors;

	while (num % 2 == 0) {
		primeFactors.insert(2);
		num /= 2;
	}

	for (int i = 3; i <= sqrt(num); i += 2) {
		while (num % i == 0) {
			primeFactors.insert(i);
			num /= i;
		}
	}

	if (num > 2) {
		primeFactors.insert(num);
	}

	return (primeFactors.size() % 2 == 0);
}

 

느낀 점

소인수의 개수가 짝수라는 점을 약수의 개수가 짝수라는 것으로 잘못 이해해서 30분만에 끝날 코드가 30분을 더 잡아먹게 되었다. 이 부분을 잘못 이해한지 모르고 다른 부분만 백날 뒤지고 조건을 잘못 이해했는지 읽어보다가 더 헤맸다. 다른 백준 문제들처럼 아주 명료하게 문제가 구성되어 있었다면 문제의 등급이 Silver3씩이나 되지는 않을 것이다. 즉, 이번 문제는 알고리즘보다는 국어실력을 더 테스트하고 있었다.

헷갈리지 않기 위해 블로그로 정리하면서까지 문제를 풀었는데도 헤맸다는게 너무 아쉬웠다.