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

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

 

문제

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

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

---

풀이

간단한 정수론 문제입니다. K = A × B 형태로만 분할할 수 있으므로 최종적인 형태는 소인수분해된 형태임을 예측할 수 있습니다.

즉, K가 100일 때, 100 = 2^2 × 5^2 이므로 4개의 소인수로 분해됩니다.

 

이 문제는 흠집이 제일 많이 생긴 슬라임의 흠집 개수의 최소를 구하는 문제입니다. 흠집을 최소화하기 위해선 가능한한 완전 이진 트리 형태로 분할하는게 트리의 레벨을 최소로 할 수 있으니 좋겠죠. 즉, 앞에 구한 소인수의 개수를 n이라 하면 n개의 리프 노드를 가지는 트리의 레벨을 구하는 문제입니다.

 

완전 이진 트리니까 리프 노드의 수가 2의 제곱수인 경우는 log2(n)이 답이 되고, 아닌 경우에는 log2(n) + 1이 답이 됩니다.

---

코드

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

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int k;
  cin >> k;
  // 소인수 개수
  int cnt = 0;
  for (int i = 2; i * i <= k; i++)
    while (k % i == 0) {
      k /= i;
      cnt++;
    }
  if (k != 1)
    cnt++;
  // 답
  if (log2(cnt) == (int)log2(cnt))
    cout << log2(cnt);
  else
    cout << (int)log2(cnt) + 1;
  return 0;
}