99클럽 코테 스터디 13일차 TIL 그리디(고양이는 많을수록 좋다)

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

 

<알고리즘>

이런문제는 결과값을 가지고 입력값을 만들어가는 경우를 생각해야 한다.

그리고 그 과정에서 최소 연산을 할 수 있도록 해야하는데, 이 문제의 경우는 생성과 복제 중 복제이다.

결과값에서 최대한 복제를 할 수 있는 한 하고 생성을 해서 입력값으로 만들어 가는 연산의 수를 구하면 된다.

즉, 6일 때 -> 3(최대 2배로 복제) -> 2(최대 2배 이하로 복제할 경우) -> 1(최대 2배로 복제) -> 0(생성) => 4가 된다.

이를 코드로 구현하면 아래와 같다.

** 입력값이 0일 경우엔 무조건 0임을 고려해주어야 한다

 

<제출 코드>

package STUDY.Week02;

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

public class Day13_BOJ_27961_고양이는많을수록좋다 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long cnt = 0;
        if(n != 0) {
            while(true){
                if(n >= 2){
                    n = (long) Math.ceil(n / 2.0);
                    cnt++;
                }
                if(n == 1) {
                    cnt++;
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}