[TIL] 99클럽 코테 스터디 13일차 TIL + 백준 27961 고양이는 많을 수록 좋다.

문제 풀이

 

문제 탐색하기

예제를 확인하다보면 고양이가 1마리가 되고나서 N마리의 고양이를 키우기 위해서 고양이의 수를 2배로 계속 복제하는 카운트를 통해 최소 행동 횟수를 알 수 있습니다.

예를 들어 33마리의 고양이를 키우고 싶다면 아래와 같습니다.

0 -(생성마법)> 1 -(복제마법)> 2 -(복제마법)> 4 -(복제마법)> 8 -(복제마법)> 16 -(복제마법)> 32 -(복제마법)> 33

 

복제마법을 사용할 때 계속 2배로 복제하다가 2배로 복제한 수가 원하는 N의 값 보다 커지면 N이 되는 값 만큼 더해주면 됩니다. 

마법을 사용하는 횟수를 카운트 하였을 때 마지막 복제 마법의 카운트와 2배 복제한 수가 N의 값보다 커질때의 카운트가 같기때문에 

그 복제한 수가 N보다 커질때 while문을 종료하면 됩니다.

결과는 while문에서 구한 카운트와 생성마법을 사용하는 1회를 더해서 출력해주면 되는데 이때 N이 0으로 주어지는 경우를 고려해서 답을 출력해주면 됩니다.

 

문제 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());

        int cnt = 0;
        long x = 1;
        while(N > x){
            cnt++;
            x = x*2;
        }

        cnt = N == 0 ? 0 : cnt+1;

        System.out.println(cnt);
    }
}