[백준 - 14715][GOLD 5][해설 X] - 전생했더니 슬라임 연구자였던 건에 대하여 (Easy) (JAVA)

문제 링크

---

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

 

문제

---

안녕? 내 이름은 ntopia!

나는 원래 지구에 살고 있던 평범한 20대 청년이었어. 어느 날 길을 걷다가 괴한의 칼에 찔려 죽어버렸어. 그런데 이게 무슨 일이람! 정신을 차려보니 이세계에 떨어져 버렸지 뭐야. 여기에서 나는 슬라임을 전문으로 연구하는 슬라임 연구자가 되어버린 것 같아. 나는 지금 아주 중요한 연구를 진행하고 있어. 이 연구가 성공하면 나는 내가 살던 세계로 돌아갈 수 있게 될 거야. 이 연구를 도와주지 않겠니?

이곳의 슬라임은 모두 슬라임 에너지라는 것을 갖고 있고 그 양은 2 이상의 자연수로 표현돼. 나는 슬라임을 분할했을 때 슬라임 에너지가 어떻게 변화하는지에 대해 연구하고 있어.

슬라임 분할 과정은 1마리를 분할해서 2마리를 만들어내는 식으로 이루어져. K만큼의 슬라임 에너지를 가진 슬라임이 있었다고 해보자. 이 슬라임을 적절히 분할하면 A만큼의 에너지를 갖는 슬라임과 B만큼의 에너지를 갖는 슬라임을 만들 수 있고 (A, B는 2 이상의 자연수), 항상 K = A × B 를 만족해. 이렇게 분할하다보면 언젠가는 분할이 되지 않는 슬라임도 생기겠지?

그리고 슬라임 분할 기술이 아직 완벽하지 않아서 슬라임을 분할할 때마다 흠집이 하나씩 생기게 돼. 구체적으로, 흠집이 T개인 슬라임을 분할하면 흠집이 T + 1개인 슬라임 2마리가 생기는 것이지.

 에너지가 24이고 흠집이 1개인 슬라임을 분할한 모습. 에너지가 4이고 흠집이 2개인 슬라임과 에너지가 6이고 흠집이 2개인 슬라임으로 분할되었다.

나에겐 지금 슬라임 에너지가 K이고 흠집이 하나도 없는 슬라임이 있어. 이 슬라임을 분할하고 또 분할해서 분할이 가능한 슬라임이 존재하지 않을 때까지 마구마구 분할해야해. 그렇게 다 분할하고나면 마지막에 남은 슬라임들에 흠집이 적당히 생겼겠지? (물론 생기지 않았을 수도 있어) 그 슬라임들 중에서 흠집이 제일 많이 생긴 녀석의 흠집 개수가 최소가 되도록 분할을 적절히 수행하는 것이 내 연구의 목표야.

내 연구를 도와줘! 부탁이야!!

 

입력

---

첫 번째 줄에 처음 주어진 슬라임의 에너지 K (2 ≤ K ≤ 1, 000, 000) 가 주어진다.

 

출력

---

슬라임을 끝까지 분할했을 때, 가장 많이 생긴 흠집의 개수의 최솟값을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        boolean valid = true;
        int count = 1;  //소인수 분해 횟수

        //소인수 분해 횟수 구하기
        while(valid){
            valid = false;

            for(int i=2;i<=Math.sqrt(N);i++){
                //소인수 분해를 할 수 있다면 인수 분해 진행
                if(N % i == 0){
                    count++;
                    N/=i;
                    valid= true;
                    break;
                }
            }
        }

        //완전 이진트리의 높이 구하기
        int height = (int)Math.ceil(Math.log(count)/Math.log(2));

        System.out.println(height);
    }
}

 

 

실행 결과

---

 

팁

---

 

• 완전이진트리의 높이 = log2(리프노드의 개수)
• 소인수분해를 진행할 때 루트 N까지만 진행하면 저 효율적인 시간복잡도로 인수분해를 진행할 수 있다.