[백준 14715번] 전생했더니 슬라임 연구자였던 건에 대하여 (easy) (C++)

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

14715번: 전생했더니 슬라임 연구자였던 건에 대하여 (Easy)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int func(int n)
{
    int cnt = 0;
    int tmp = n;

    for(int i=2; i<n; i++)
    {
        if(n%i==0) 
        {
            while(tmp%i==0) //소인수 분해
            {
                cnt++; //노드 추가
                tmp /= i;
            }
        } 
    }
    if(cnt == 0) return 1; //소수는 1
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int K;
    cin >> K;
    
    cout << ceil(log2(func(K))); //완전이진트리의 깊이가 곧 흠집의 개수

    return 0;
}

분할이 안될때까지 하기에 결국 슬라임의 값이 소수가 될때까지 분할을 한다는 말과 같다.

소인수분해를 통해서 완전이진트리의 노드의 갯수를 구해준다.

여기서 소인수분해를 통해 구한 각 값이 완전이진트리의 맨 아래 값에 위치한다. (노드)

완전이진트리의 깊이가 곧 흠집의 갯수인데, 완전이진트리의 깊이는 노드의 갯수에 log2를 씌워준 값이다.