반응형
문제 출처 :
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 |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[3023번] 마술사 이민혁 (0) | 2017.11.11 |
---|---|
[2367번] 파티 (0) | 2017.11.10 |
[3022번] 식사 예절 (0) | 2017.11.10 |
[14891번] 톱니바퀴 (0) | 2017.11.09 |
[5558번] 치~즈 (0) | 2017.10.25 |