C++로 검소한 수(Frugal Number) 판별하기

문제 개요

이 문제에서는 양의 정수 N이 하나 주어지며, 주어진 수가 검소한 수(Frugal Number)인지 아닌지를 판별하는 프로그램을 작성해야 합니다.

검소한 수란 무엇일까요?

검소한 수(Frugal Number)란, 수 자체의 자릿수가 해당 수를 소인수분해하여 표기할 때 필요한 자릿수보다 엄격하게 큰 수를 의미합니다.

예시 — 625의 소인수분해 결과는 5⁴입니다.

• 625의 자릿수: 3자리
• 5⁴ 표기의 자릿수: 2자리

3은 2보다 크므로, 625는 검소한 수입니다.

가장 작은 검소한 수들은 다음과 같습니다: 125, 128, 243, 256, 343, 512, 625 등.

예제로 문제 이해하기

입력: n = 128
출력: Frugal number (검소한 수)
설명:
128의 인수는 2^7이며, 표기 자릿수는 2입니다.
128 자체의 자릿수는 3입니다.
따라서 128은 검소한 수입니다.

풀이 접근 방법

이 문제를 해결하는 가장 직관적인 방법은 주어진 수 n이 검소한 수인지 직접 확인하는 것입니다. 구체적인 절차는 다음과 같습니다.

1. n의 모든 소인수를 구합니다.
2. 각 소인수와 그 지수를 포함한 소인수분해 표기의 총 자릿수를 계산합니다.
3. 원래 수 n의 자릿수를 계산합니다.
4. n의 자릿수가 소인수분해 표기의 자릿수보다 크면 검소한 수이고, 그렇지 않으면 검소한 수가 아닙니다.

C++ 구현 예제

아래는 위 풀이 방식을 실제로 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;

vector<long int> calcPrimeNum(long int n){

    bool primeNos[n + 1];
    memset(primeNos, true, sizeof(primeNos));
    for (int i = 2; i * i <= n; i++) {
       if (primeNos[i] == true) {
          for (int j = i * 2; j <= n; j += i)
             primeNos[j] = false;
       }
    }
    vector<long int> allPrimeNumbers;
    for (int i = 2; i < n; i++)
       if (primeNos[i])
          allPrimeNumbers.push_back(i);
    return allPrimeNumbers;
}
int countNumDigits(long int n){

    long long int num = n;
    int digitCount = 0;
    while (num != 0) {
       num = num / 10;
       digitCount++;
    }
    return digitCount;
}
bool isFrugalNum(long int n){

    vector<long int> primeNum = calcPrimeNum(n);
    long int num = n;
    long int factorDigitCount = 0;
    for (int i = 0; i < primeNum.size(); i++) {
       if (num % primeNum[i] == 0) {
          long int k = 0;
          while (num % primeNum[i] == 0) {
             num = num / primeNum[i];
             k++;
          }
          if (k == 1)
             factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]);
          else if (k != 1)
             factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]) + countNumDigits(k);
       }
    }
    return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}
int main(){

    long int n = 625;
    cout<<"The number "<<n<<" is ";isFrugalNum(n)? cout<<"a Frugal number\n" : cout << "not a Frugal number\n";
    return 0;
}

코드 동작 원리

• calcPrimeNum(): 에라토스테네스의 체를 이용해 n 미만의 모든 소수를 구합니다.
• countNumDigits(): 숫자를 10으로 반복해서 나누며 자릿수를 셉니다.
• isFrugalNum(): 각 소수로 n을 나누어 지수 k를 구하고, 지수가 1이면 소수의 자릿수만, 1보다 크면 소수와 지수의 자릿수를 모두 합산합니다. 최종적으로 n의 자릿수가 합산된 자릿수보다 크면 true를 반환합니다.

실행 결과

The number 625 is a Frugal number