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

문제 출처 :

https://www.acmicpc.net/problem/14715

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

결국 이 문제는 슬라임이 최종까지 분해될때 어떻게 되는지 처음으로 묻고있다.

최종적으로 분리되어 더이상 분리할 수 없을때는 결국 모든 슬라임은 소수로 이루어짐을 파악할 수 있다.

따라서 우리는 입력받는 수 n이 최종적으로 분리되면 소수 a1 * a2 * ... * ak개로 나타남을 파악할 수 있고

이 소수를 적절히 나열하여 완전이진트리를 최대한 형성시키게 된다면 우리는 최소 흉터를 찾아 낼 수 있게된다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <iostream> #include <cstdio> #include <queue> #include <vector> #include <cmath>   #define fastio() ios::sync_with_stdio(0),cin.tie(0);   using namespace std;   typedef pair<int, int> pii;   int func(int now) {     int cnt = 0;     int tmp = now;       for (int i = 2; i < now; i++)         if (now % i == 0)             while (tmp % i == 0)                 cnt++, tmp /= i;       if (cnt == 0)         return 1;       return cnt; }   int main() {     int n;     scanf("%d", &n);       cout << ceil(log2(func(n)));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus